Problem Statement in English

You’re given an integer array nums of size n where each element is in the range [1, n].

Your task is to find the duplicate number in the array. With $O(1)$ space and $O(n)$ time.

Approach

Whooooo! This is a fun one.

Doing this in $O(1)$ space is a bit tricky, and in my opinion, unintuitive.

The approach is to use the fast and slow pointer technique. Look here for an example. We first wait for the two pointers to meet. Once they meet, we reset one of the pointers to the start of the array and move both pointers at the same speed. The point at which they meet is the duplicate number.

But you ask, there are no links here!!! How do we move the pointers? And what “pointers”?? Yea, so…

Since there are $n$ elements in the list, and each is within the range $[1, n]$, we can use the elements as pointers. So if we consider that each element tells us which index to jump to next, we’ve established a linked list.

Now all we need to do is ensure that one pointer (the fast one), makes 2 jumps for each jump made by the slow pointer.

This way, when they meet, we know we’ve got a cycle, and we can reset one of the pointers to the start of the array and move them at the same speed. The point at which they meet is the duplicate number.

Solution in Python


class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0

        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]

            if slow == fast:
                break

        slow2 = 0

        while slow2 != slow:
            slow = nums[slow]
            slow2 = nums[slow2]

        return slow2

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we only use a couple integer pointers

Mistakes I Made

I had to look this one up :(

And we are done.