How can you find duplicates in an array of numbers from 0 to n-1 in O(n) time and O(1) space?

Finding Duplicates in O(n) Time and O(1) Space

Given an array of n elements containing numbers from 0 to n-1, where some numbers may appear multiple times, the goal is to find the duplicate elements in O(n) time and using constant memory space.

To achieve this, we can utilize an intriguing approach that doesn't require additional data structures like hash tables.

The proposed algorithm operates as follows:

1. Permutation Loop:

   • Iterate through the array for i from 0 to n-1.
   • Inside this loop, perform the following steps until A[A[i]] equals A[i]. This implies that the element A[i] is in its correct position.
   • Swap A[i] with A[A[i]]. This effectively moves the element A[i] one step closer to its correct position.

2. Duplication Identification Loop:

   • Iterate through the array once more, from i from 0 to n-1.
   • If A[i] does not equal i, it means that there is a duplicate of i at index A[i].
   • Print A[i] as a duplicate.

This algorithm ensures that all duplicate elements are identified. The outer loop runs n times, while the inner loop runs at most n-1 times. Therefore, the algorithm runs in O(n) time. It doesn't use any additional data structures, which means it operates in O(1) space.

The provided code exemplifies the algorithm's implementation in C .

The above is the detailed content of How can you find duplicates in an array of numbers from 0 to n-1 in O(n) time and O(1) space?. For more information, please follow other related articles on the PHP Chinese website!