# 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 2 3 4 5 |
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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
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 2 |
1 3 |

Time Complexity – Single Traversal – **O(n)**

Space complexity – **O(1)**

## Recommended Posts

- Find the Largest and Smallest Number in Unsorted Array – O(n)
- Running time in Big O notation for Java Arrays Algorithms
- Find Second Largest Element in an Unsorted Array – O(n)
- Program to reverse a string or word
- Efficient sorting mechanism for Unsorted Array – List Insertion Sort
- Find all possible combinations of numbers to print given sum

## Leave a Reply