Problem Statement
You are given an unsorted array that may contain duplicates. A number k that is less than the size of the array is also provided. Write a function that takes an array, an integer k, and the size of an array n, as input and the function returns true if the array contains duplicates within k distance.
Must Recommended Topic, Hash Function in Data Structure.
Examples:
Input:
k = 2, arr[] = {2, 2, 1, 4, 1, 2}
Output:
true
2 is repeated at distance 2.
Input:
k = 3, arr[] = {9, 2, 1, 8, 4, 5}
Output:
false
Input:
k = 4, arr[] = {6, 2, 8, 6, 5}
Output:
true
6 is repeated at distance 4.
Naive approach
The first and easiest solution is Running two loops. The inner loop checks all items that are within k distance of "arr[i]" after the outer loop chooses every element "arr[i]" as a starting element. This solution has a time complexity (kn).
Algorithm
- Create a function that takes arr[], k, and n as parameters.
- Run the first loop to traverse the whole array.
- Inside this loop, start another loop to search next k-1 elements
- if their duplicates are present, return True
- Else False
Let's take an example to better understand the algorithm.
k = 2, arr[] = {9,5,5,4}
Step 1: Take Array as input
Step 2: Take the first element of the array = 9 and initialize a variable w=k
Step 3: Match with the next element and if the element is not equal reduce the value of w
Step 4: if the value of w<0, come out of the loop and take another element of the array and perform step 3 and step 4.
Step 5: The element 5 matches with the next element and returns Yes.
Code in C++
Implementation in C++ to check if a given array contains duplicate elements within k distance from each other.
#include <bits/stdc++.h>
using namespace std;
bool checkDuplicates(int arr[], int n, int k)
{
for (int i = 0; i < n; i++) {
int window = k;
for(int j=i+1;window>0 && j<n;j++){
if (arr[i] == arr[j])
return true;
window--;
}
}
return false;
}
int main()
{
int arr[] = { 14, 4, 7, 4, 9, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (checkDuplicates(arr, n, 3))
cout << "Yes";
else
cout << "No";
}
Output
YesCode in Java
Implementation in Java to check if a given array contains duplicate elements within k distance from each other.
public class Main
{
public static boolean checkDuplicates(int[] arr, int n, int k)
{
for (int i = 0; i < n; i++)
{
int window = k;
for (int j = i + 1;window > 0 && j < n;j++)
{
if (arr[i] == arr[j])
{
return true;
}
window--;
}
}
return false;
}
public static void main(String[] args)
{
int[] arr = {14, 4, 7, 4, 9, 4, 6};
int n = arr.length;
if (checkDuplicates(arr, n, 3))
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
}
Output
YesCode in Python
Implementation in Python to check if a given array contains duplicate elements within k distance from each other.
def main():
arr = [14, 4, 7, 4, 9, 4, 6]
n = len(arr)
if Globals.checkDuplicates(arr, n, 3):
print("Yes", end = '')
else:
print("No", end = '')
class Globals:
@staticmethod
def checkDuplicates(arr, n, k):
for i in range(0, n):
window = k
j = i+1
while window>0 and j<n:
if arr[i] == arr[j]:
return True
window -= 1
j += 1
return False
if __name__ == "__main__":
main()
Output
Yes
Time complexity: 0(kn)
There are nested loops present in the solution and the time complexity will depend on the condition of the loop. The first loop is running n time and the second one depends on the parameter k hence time complexity will be 0(kn).
Space Complexity-O(1)
We haven't stored the value anywhere in the code hence space complexity will be O(1)
117+ registered 