Find Numbers Repeated in Array in O(n) Time and O(1) Space

Given an input array of integers, your goal is to find the numbers repeated or duplicates present in the array in an effective way without using Java Collections. Note, you need to achieve this in O(n) time i.e., you should be able to find the results by traversing through the array only once.

Algorithm:

Below is the efficient algorithm for doing this

1) Declare/provide input array
2) Traverse through the array
   2.1) Check for the sign of A[abs(A[i])]
   2.2) If positive then make it by negative A[abs(A[i])] = - A[abs(A[i])]
   2.3) Else the current element of the array is repeated/duplicated. Print the duplicate.

In any given array, every element present at a given index is going to reference another index if the number is repeated. In order to track the references of the index, we make it negative whenever it is referenced for the first time. That way we can easily detect the duplicate whenever it is referenced again.

Solution to find numbers repeated or duplicates

package com.sneppets.dsalgo.examples;

/**
 * Program to find duplicates in array in O(n) time without using collections
 * Note: This code will run only for those numbers which are less than array size.
 * @author sneppets.com
 *
 */
public class DuplicatesInArrayExample1 {
	
	public static void main(String[] args)
	{
		int inArray[] = {2, 4, 1, 7, 3, 5, 1, 3};
		int arraySize = inArray.length;
		findDuplicates(inArray, arraySize);		
	}
	
	private static void findDuplicates(int[] inArray, int arraySize) {
		
		//Traverse through the array
		for(int i=0; i<arraySize; i++)
		{
			//check if sign for "A[abs(A[i])]" is positive
			if (inArray[Math.abs(inArray[i])] >= 0)
			{				
				//if positive, then make it negative by "A[abs(A[i])]=-A[abs(A[i])]"
				inArray[Math.abs(inArray[i])] = - inArray[Math.abs(inArray[i])];
			}
			else
			{	//current element of the array is repetitive
				System.out.println(Math.abs(inArray[i]) +" ");
			}
		}	
		
	}

}

Note: This code will run only for the numbers which are less than array size.

Output

1 
3

Time Complexity – Single Traversal – O(n)

Space complexity – O(1)

Find Numbers Repeated in Array in O(n) Time and O(1) Space

Algorithm:

Solution to find numbers repeated or duplicates

Recommended Posts

Reference