Check if a 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. 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 method int 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 method int 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 other def 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 method arr = [ 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 given array contains duplicate elements within 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. |
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 method int 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 Code if __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 given array 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> |
Yes
Time Complexity: O(N).
Auxiliary Space: O(N) for using an unordered set.
Contact Us