Write a function to determine whether duplicate elements in a given ar

1.	Write a function to determine whether duplicate elements in a given array are within a given distance of each other.
Answer» Input: arr[] = {1, 2, 3, 4, 2, 1, 2} range=3 Output: True class Solution { public: bool checkDuplicatesWithinRange(vector<int> arr, int range) { // Creating an empty hashset unordered_set<int> myset; // Traversing the input array for (int i = 0; i < arr.size(); i++) { // If already present in hashset, then we found a duplicate within range distance if (myset.find(arr[i]) != myset.end()) return true; // Add this item to hashset myset.insert(arr[i]); // Remove the range+1 distant item from the hashset if (i >= range) myset.erase(arr[i-range]); } return false; } }; Time Complexity: O(n) Space Complexity: O(n)

Write a function to determine whether duplicate elements in a given array are within a given distance of each other.

Answer»

Input: arr[] = {1, 2, 3, 4, 2, 1, 2} range=3

Output: True

class Solution {
public:

bool checkDuplicatesWithinRange(vector<int> arr, int range)
{
// Creating an empty hashset
unordered_set<int> myset;

// Traversing the input array
for (int i = 0; i < arr.size(); i++)
{
// If already present in hashset, then we found a duplicate within range distance
if (myset.find(arr[i]) != myset.end())
return true;

// Add this item to hashset
myset.insert(arr[i]);

// Remove the range+1 distant item from the hashset
if (i >= range)
myset.erase(arr[i-range]);
}
return false;
}
};

Time Complexity: O(n)

Space Complexity: O(n)

Discussion

No Comment Found

Related InterviewSolutions

What is topological sorting in a graph?
Given an m x n 2D grid map of '1’s which represents land and '0’s that represents water return the number of islands (surrounded by water and formed by connecting adjacent lands in 2 directions - vertically or horizontally).
Print Left view of any binary trees.
Write Java code to count number of nodes in a binary tree
Write a recursive function to calculate the height of a binary tree in Java.
Write a function to determine whether duplicate elements in a given array are within a given distance of each other.
Implement LRU(Least Recently Used) Cache
Write a function to find number of structurally unique binary trees are possible
Write a function to connect nodes at the same level of a binary tree
Write a function to implement Quicksort on Doubly Linked List