Author : Aakash Tandale
All Tutorials on Hashing are listed here: https://www.desiqna.in/tag/hashing_tutorials
It is recommended to go through previous hashing tutorials to get a better understanding.
PART 7 (Check if the given array contains duplicate elements within k distance from each other .) :
Problem: Check if the following given array contains duplicate elements within k distance from each other.
Given an unsorted array that may contain duplicates. Also given a number k which is smaller than the size of the array, returns true if the array contains duplicates within k distance.
Example-1:
Input: k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}
Output: false
All duplicates are more than k(3) distance away.
1...1(has a distance of 4)
2...2(has a distance of 4)
3...3 and 4...4 are similar
Even if we find one duplicate number having a distance less than equal to k(<=k), we would return true.
Example-2:
Input: k = 3, arr[] = {1, 2, 3, 1, 4, 5}
Output: true
1 is repeated at distance 3(3<=k hence we return true).
Igdf
Approach 1: Brute-Force
A Naive solution is to run two loops. The outer loop picks every element ‘arr[i]’ as a starting element, and the inner loop compares all elements which are within k distance of ‘arr[i]’.
Time complexity: O(k*n)
Space complexity: O(1)
Piece of code(C++) :-
Approach 2: Hashing Approach
In order to make optimization first, we need to figure out what kind of repetitive work we are doing. In our brute force, we are iterating an array over and over again so we need to remove this work.
Here the "Hashing" comes into the picture.
We can use the map or set depending on the problem statement.
Here we will be using the unordered map which contains
key--> element of an array
value--> index of element in array
Algorithm:
While traversing an array from left to right we need to consider two situations.
1] If the array element is already present in our map then get its position from a map and calculate the difference between the current index and the position that we have fetched from the map.
-> if the difference is greater than k then update the position of the current element in the map
-> if the difference is less than k then simply return true.
2] If the array element is not present in our map then just insert it with its index.
Time complexity: O(n)
Space complexity: O(n)
let's take a simple example arr={1,2,3,1} and k=3
From the given array up to the index 2, our map will look like this:-
at index 3 we see that we already have an element that is present in the map so we get its position and check if it lies within k distance or not.
Piece of code(C++) :- https://ideone.com/6iRmdE
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials