numbers repeated or duplicates

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

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

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

Output

Time Complexity – Single Traversal – O(n)

Space complexity – O(1)

Recommended Posts

Reference

Leave a Reply

avatar
  Subscribe  
Notify of