Given an unsorted array that may contain duplicates. Also given a number k which is smaller than the size of the array. Write a function that returns true if the array contains duplicates within k distance.
Examples:
Input: k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}
Output: false
All duplicates are more than k distance away.
Input: k = 3, arr[] = {1, 2, 3, 1, 4, 5}
Output: true
1 is repeated at distance 3.
Input: k = 3, arr[] = {1, 2, 3, 4, 5}
Output: false
Input: k = 3, arr[] = {1, 2, 3, 4, 4}
Output: true
A Simple 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]’. The time complexity of this solution is O(k * n).
Implementation:
C++
// C++ program to Check if a given array contains duplicate// elements within k distance from each other#include <bits/stdc++.h>using namespace std;bool checkDuplicatesWithinK(int arr[], int n, int k){ // traversing the input array for (int i = 0; i < n; i++) { int j = i + 1; int range = k; // searching in next k-1 elements if its duplicate // is present or not while (range > 0 and j < n) { if (arr[i] == arr[j]) return true; j++; range--; } } return false;}// Driver method to test above methodint main(){ int arr[] = { 10, 5, 3, 4, 3, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); if (checkDuplicatesWithinK(arr, n, 3)) cout << "Yes"; else cout << "No";}// This article is contributed by Arpit Jain |
C
// C program to Check if a given array contains duplicate// elements within k distance from each other#include <stdbool.h>#include <stdio.h>bool checkDuplicatesWithinK(int arr[], int n, int k){ // traversing the input array for (int i = 0; i < n; i++) { int j = i + 1; int range = k; // searching in next k-1 elements if its duplicate // is present or not while (range > 0 && j < n) { if (arr[i] == arr[j]) return true; j++; range--; } } return false;}// Driver method to test above methodint main(){ int arr[] = { 10, 5, 3, 4, 3, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); if (checkDuplicatesWithinK(arr, n, 3)) printf("Yes"); else printf("No");}// This code is contributed by Aditya Kumar (adityakumar129) |
Java
public class GFG { /* Java program to Check if a given array contains duplicate elements within k distance from each other */ public static boolean checkDuplicatesWithinK(int[] arr, int n, int k) { // traversing the input array for (int i = 0; i < n; i++) { int j = i + 1; int range = k; // searching in next k-1 elements if its // duplicate is present or not while (range > 0 && j < n) { if (arr[i] == arr[j]) { return true; } j++; range--; } } return false; } // Driver method to test above method public static void main(String[] args) { int[] arr = { 10, 5, 3, 4, 3, 5, 6 }; int n = arr.length; if (checkDuplicatesWithinK(arr, n, 3)) { System.out.print("Yes"); } else { System.out.print("No"); } }}// This article is contributed by Aarti_Rathi |
Python3
# Python3 program to Check if a given array contains duplicate# elements within k distance from each otherdef checkDuplicatesWithinK(arr, n, k): # traversing the input array for i in range(n): j = i + 1 range_ = k # searching in next k-1 elements if its duplicate # is present or not while (range_ > 0 and j < n): if (arr[i] == arr[j]): return True j += 1 range_ -= 1 return False# Driver method to test above methodarr = [10, 5, 3, 4, 3, 5, 6]n = len(arr)if (checkDuplicatesWithinK(arr, n, 3) == True): print("Yes")else: print("No")# This article is contributed by Abhijeet Kumar(abhijeet19403) |
C#
/* C# program to Check if a givenarray contains duplicate elementswithin k distance from each other */using System;using System.Collections.Generic;class GFG { static bool checkDuplicatesWithinK(int[] arr, int n, int k) { // traversing the input array for (int i = 0; i < n; i++) { int j = i + 1; int range = k; // searching in next k-1 elements if its // duplicate is present or not while (range > 0 && j < n) { if (arr[i] == arr[j]) return true; j++; range--; } } return false; } // Driver code public static void Main(String[] args) { int[] arr = { 10, 5, 3, 4, 3, 5, 6 }; int n = arr.Length; if (checkDuplicatesWithinK(arr, n, 3)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code has been contributed by Aarti_Rathi |
Javascript
class GFG{ // javascript program to Check if a given array contains // duplicate elements within k distance from each other static checkDuplicatesWithinK(arr, n, k) { // traversing the input array for (var i=0; i < n; i++) { var j = i + 1; var range = k; // searching in next k-1 elements if its // duplicate is present or not while (range > 0 && j < n) { if (arr[i] == arr[j]) { return true; } j++; range--; } } return false; } // Driver method to test above method static main(args) { var arr = [10, 5, 3, 4, 3, 5, 6]; var n = arr.length; if (GFG.checkDuplicatesWithinK(arr, n, 3)) { console.log("Yes"); } else { console.log("No"); } }}GFG.main([]);// This code is contributed by aadityaburujwale. |
Output
Yes
Time Complexity: O(N*K).
Auxiliary Space: O(1).
Another Solution using hashing:-
We can solve this problem in Θ(n) time using Hashing. The idea is to add elements to the hash. We also remove elements that are at more than k distance from the current element. Following is a detailed algorithm.
- Create an empty hashtable.
- Traverse all elements from left to right. Let the current element be ‘arr[i]’
- If the current element ‘arr[i]’ is present in a hashtable, then return true.
- Else add arr[i] to hash and remove arr[i-k] from hash if i is greater than or equal to k
Implementation:
C++
#include<bits/stdc++.h>using namespace std;/* C++ program to Check if a given array contains duplicate elements within k distance from each other */bool checkDuplicatesWithinK(int arr[], int n, int k){ // Creates an empty hashset unordered_set<int> myset; // Traverse the input array for (int i = 0; i < n; i++) { // If already present n hash, then we found // a duplicate within k distance if (myset.find(arr[i]) != myset.end()) return true; // Add this item to hashset myset.insert(arr[i]); // Remove the k+1 distant item if (i >= k) myset.erase(arr[i-k]); } return false;}// Driver method to test above methodint main (){ int arr[] = {10, 5, 3, 4, 3, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); if (checkDuplicatesWithinK(arr, n, 3)) cout << "Yes"; else cout << "No";}//This article is contributed by Chhavi |
Java
/* Java program to Check if a given array contains duplicate elements within k distance from each other */import java.util.*;class Main{ static boolean checkDuplicatesWithinK(int arr[], int k) { // Creates an empty hashset HashSet<Integer> set = new HashSet<>(); // Traverse the input array for (int i=0; i<arr.length; i++) { // If already present n hash, then we found // a duplicate within k distance if (set.contains(arr[i])) return true; // Add this item to hashset set.add(arr[i]); // Remove the k+1 distant item if (i >= k) set.remove(arr[i-k]); } return false; } // Driver method to test above method public static void main (String[] args) { int arr[] = {10, 5, 3, 4, 3, 5, 6}; if (checkDuplicatesWithinK(arr, 3)) System.out.println("Yes"); else System.out.println("No"); }} |
Python 3
# Python 3 program to Check if a given array # contains duplicate elements within k distance# from each other def checkDuplicatesWithinK(arr, n, k): # Creates an empty list myset = [] # Traverse the input array for i in range(n): # If already present n hash, then we # found a duplicate within k distance if arr[i] in myset: return True # Add this item to hashset myset.append(arr[i]) # Remove the k+1 distant item if (i >= k): myset.remove(arr[i - k]) return False# Driver Codeif __name__ == "__main__": arr = [10, 5, 3, 4, 3, 5, 6] n = len(arr) if (checkDuplicatesWithinK(arr, n, 3)): print("Yes") else: print("No")# This code is contributed by ita_c |
C#
/* C# program to Check if a givenarray contains duplicate elements within k distance from each other */using System;using System.Collections.Generic;class GFG{ static bool checkDuplicatesWithinK(int []arr, int k) { // Creates an empty hashset HashSet<int> set = new HashSet<int>(); // Traverse the input array for (int i = 0; i < arr.Length; i++) { // If already present n hash, then we found // a duplicate within k distance if (set.Contains(arr[i])) return true; // Add this item to hashset set.Add(arr[i]); // Remove the k+1 distant item if (i >= k) set.Remove(arr[i - k]); } return false; } // Driver code public static void Main (String[] args) { int []arr = {10, 5, 3, 4, 3, 5, 6}; if (checkDuplicatesWithinK(arr, 3)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code has been contributed// by 29AjayKumar |
Javascript
<script>/* Javascript program to Check if a given array contains duplicate elements within k distance from each other */ function checkDuplicatesWithinK(arr, n, k) { // Creates an empty hashset let myset = []; // Traverse the input array for(let i=0;i<n;i++) { // If already present n hash, then we found // a duplicate within k distance if(arr.includes(arr[i])) { return true; } // Add this item to hashset myset.add(arr[i]); // Remove the k+1 distant item if (i >= k) { index = array.indexOf(arr[i - k]); array.splice(index, 1); } } return false; } // Driver method to test above method let arr = [10, 5, 3, 4, 3, 5, 6]; let n= arr.length; if (checkDuplicatesWithinK(arr, n, 3)) { document.write("Yes"); } else { document.write("No"); } // This code is contributed by rag2127 </script> |
Output
Yes
Time Complexity: O(N).
Auxiliary Space: O(N) for using an unordered set.
This article is contributed by Anuj. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
