How to Find a Duplicate in an Array of Positive Numbers with Constant Space Complexity

How do we usually find duplicates? Brute force with O(n^2) time complexity is not an option – too slow. We can do better using sort with O(n log n) or even O(n) using a data structure, like Hash Map. But these approaches require additional space, which is O(n) complexity. What if space complexity has to be constant O(1)?

I want to show an interesting approach that I came across recently. It uses linear O(n) time complexity and constant O(1) extra space (no additional data structures) to find duplicates in an array of integers. It has one con, the algorithm is modifying the input array. But it is always a trade-off when you pick a solution.

Coding problem

You have an array of positive integers [1..n]. There is one duplicate number in it. Find that number. You cannot use additional data structures.

Algorithm constraints

All integers in an input array have to be positive. So if you see in the problem description something like 1 <= nums[i] < nums.length, this approach will work. This approach temporarily changes the array's values, so I assume we can modify the input.

How it works

It is a very intuitive approach. While iterating over an array, we use the current value as the index and make the value located at the index negative. If the value at the index is already negative, we found a duplicate.

Let's walk through an example. We have an array on numbers [2,5,1,3,2,4].

On the first iteration we look at the value 2 and make value at position 2 in the array negative.

In the next iteration, value is 5, so we make the value at index 5 negative. Notice that after the first iteration the previous value at index 2 is negative now.

We keep going the same way. Here we looked back at index 1. Use absolute value to avoid errors, like accessing index -1.

Here is value 3 at the index 3, so we make the same value negative.

On this iteration current value is 2, so we look at the index of 2 and see the negative value. We marked it negative on the first iteration. So current value is our duplicate.

Let's look at the code

Javascript example:

const findDuplicate = (nums) => {
  for (let i = 0; i < nums.length; i++) {
    // index has to be positive
    const currVal = Math.abs(nums[i]);
    if (nums[currVal] < 0) return currVal;
    nums[currVal] = -nums[currVal];
  }
};

Python example:

def find_duplicate(nums):
  for i in range(len(nums)):
    curr_value = abs(nums[i])
    if nums[curr_value] < 0:
      return curr_value
    nums[curr_value] = -nums[curr_value]

Optionally we can iterate over the array one more time to make elements positive.

Conclusion

Thank you for your time! Please follow me on twitter, and if you have found a mistake or have any other questions, feel free to ask.