How to Find Duplicates in an Array with O(n) Time and O(1) Space?

Efficient Algorithm for Finding Duplicates in O(n) Time and O(1) Space

In this programming challenge, we seek an efficient algorithm to identify and print duplicate elements in an array of integers ranging from 0 to n-1, with possible repetitions. The challenge requires an algorithm that operates within O(n) time complexity and consumes only constant memory space.

One effective approach to this problem is the "array modification" technique. The algorithm works as follows:

1. First Loop:

   • Initialize a loop that iterates over each element in the array, denoted as A[i].
   • For each A[i], determine whether A[A[i]] equals A[i].
   • If not, swap A[i] with A[A[i]].

2. Second Loop:

   • Reset the loop to iterate over each A[i] again.
   • For any A[i] that does not equal i, print A[i]. This step identifies the duplicate elements because any non-duplicate element will have A[A[i]] equal to i (i.e., it is in its correct position).

This algorithm operates in O(n) time as each element is checked and modified at most once in the first loop. Additionally, since no additional data structures are used, it utilizes only O(1) space.

For example, consider the input array {1, 2, 3, 1, 3, 0, 6}. After running the algorithm, the array is modified as follows:

[1, 2, 3, 1, 3, 0, 0]

The second loop then prints the duplicate elements, 1 and 3.

The above is the detailed content of How to Find Duplicates in an Array with O(n) Time and O(1) Space?. For more information, please follow other related articles on the PHP Chinese website!