Given an array of n elements which contains integers from 0 to n-1 only. The numbers can appear any number of times. Find the repeating numbers. Example: Array: {2, 4, 1, 2, 6, 1, 6, 3, 0} Output: [1, 2, 6]
Video coming soon!
Subscribe for more updates
Algorithm/Insights
Method 1: Naive Solution Use 2 loops to find duplicates in the array. In outer loop, pick each element one by one and in inner loop check if duplicate exists for that element in the array. Time Complexity: O(n^2) Space Complexity: O(1)
Method 2: Use extra space Since the numbers are in the range 1 to n-1, we can create a count array that will store the count of the numbers in the array. count[i] represents number of times element i occurs in the array. In another traversal, find the elements that have count > 1 Time Complexity: O(n) Space Complexity: O(n)
Method 3: Traverse the array once and keep reversing the sign of element at array[i]th position. While traversing, if the sign of array[i]th element is already negative, add it to the duplicates list. Finally, return duplicates list. Time Complexity: O(n) Space Complexity: O(1)
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.
Thanks, -Team IDeserve
Algorithm Visualization
Code Snippet
package com.ideserve.questions.saurabh;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* Given an array of n elements which contains integers from 1 to n-1 only.
* The numbers can appear any number of times. Find the repeating numbers.
*
* @author Saurabh
*/
public class FindDuplicates {
public static Set<Integer> getDuplicatesNaive(int[] array) {
Set<Integer> duplicates = new HashSet<Integer>();
for(int i = 0; i < array.length; i++) {
for(int j = i+1; j < array.length; j++) {
if(array[i] == array[j]) {
duplicates.add(array[i]);
}
}
}
return duplicates;
}
public static Set<Integer> getDuplicatesExtraSpace(int[] array) {
int n = array.length;
Set<Integer> duplicates = new HashSet<Integer>();
int[] count = new int[n];
// Initialize count of all numbers to 0
for(int i = 0; i < n; i++) {
count[i] = 0;
}
// Set the count of all elements in count array
for(int i = 0; i < n; i++) {
count[array[i]]++;
}
// Check for duplicates
for(int i = 0; i < n; i++) {
if(count[i] > 1) {
duplicates.add(i);
}
}
return duplicates;
}
public static Set<Integer> getDuplicates(int[] array) {
int n = array.length;
Set<Integer> duplicates = new HashSet<Integer>();
for(int i = 0; i < n; i++) {
// Make the array element at index array[i] negative if it is positive
if(array[Math.abs(array[i])] > 0) {
array[Math.abs(array[i])] = -array[Math.abs(array[i])];
} else {
// If the element at index array[i] is negative, it means we have seen it before, so it is a duplicate
duplicates.add(Math.abs(array[i]));
}
}
return duplicates;
}
public static void main(String[] args) {
int[] array = {2, 4, 1, 2, 6, 1, 6, 3, 5};
Set<Integer> duplicates = getDuplicates(array);
System.out.println(Arrays.toString(duplicates.toArray()));
}
}
Contribution
Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.
Saurabh Kumar
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.