Find duplicates in an integer array

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)


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