Last Updated: 5 Oct, 2020
Contains Duplicate ll
Moderate
Asked in company
Given an array 'arr' of 'N' integers and an integer 'K'. The array 'arr' may contain duplicate integers. Return "true" if the array contains any duplicate element within the 'K' distance from each other, otherwise, return "false".
Input format :
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
Then the T test cases follow:
The first line of each test case contains two single space-separated integers 'N', and 'K', denoting the size of the array 'arr' and the distance respectively.
The second line of each test case contains 'N' single space-separated integers, elements of the array.
Output format :
For each test case, print “true” if the array contains any duplicate element within the 'K' distance from each other, otherwise, print "false".
Result for each test case will be printed in a separate line.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= K <= 10^5
-10^9 <= arr[i] <= 10^9
Time Limit: 1sec
Approaches
The naive approach is to run two loops, the outer loop will pick each element one by one.
The inner loop compares all elements which are within ‘K’ distance from and with the currently selected element.
If the selected element matches with any of the elements that we are comparing in the inner loop then it means there is a duplicate.
We need to check if the duplicate exists at a distance of ‘K’.
- We can do that by storing the element and its index in a map ‘MP’.
- Now iterate over the array, if ‘ARR[i]’ doesn't exist in the map, then add ‘ARR[i]’ and ‘i’ in the map.
- If ‘ARR[i]’ exists in the map then:
- If ‘i’ - ‘MP['ARR[i]']’ is less than equal to ‘K’, then return true. As the distance of the last occurrence of ‘ARR[i]’ is less ‘K’.
- Else update ‘MP[’ARR[i]']' by ‘i’. (Updating last occurrence index of ‘ARR[i]’.
- Return false in all other case.
We can use the sliding window technique. The idea is to process every window of size ‘K’ one at a time and store it into Set, now if the element is repeated in a window of size ‘K’ then we can say there is a duplicate within ‘K’ distance.
- Initially, our window will contain the first ‘K’ element which is stored in Set.
- Then for each remaining element, If it is already in the window return true. Otherwise, add it to the window. While adding the element in the window we have to also remove (i- ‘K’ - 1)th element from the current window i.e our Set.