Find the Duplicate Number

MEDIUM

Description

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

1 <= n <= 10⁵
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

Approaches

Checkout 3 different approaches to solve Find the Duplicate Number. Click on different approaches to view the approach and algorithm in detail.

Floyd's Cycle Detection (Tortoise and Hare)

Treat array elements as pointers to indices and use Floyd's cycle detection algorithm to find the duplicate.

Algorithm

Initialize two pointers (tortoise and hare) at the start
Move tortoise one step and hare two steps until they meet
Reset tortoise to start
Move both pointers one step until they meet again
Return the meeting point as the duplicate

This approach uses Floyd's Cycle Detection algorithm. Since the numbers are in range [1,n] and there's a duplicate, we can treat array values as pointers forming a linked list, which will have a cycle. The duplicate number is the entry point of the cycle.

public int findDuplicate(int[] nums) {
    // Find the intersection point of the two pointers
    int tortoise = nums[0];
    int hare = nums[0];
    
    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
    } while (tortoise != hare);
    
    // Find the entrance to the cycle
    tortoise = nums[0];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }
    
    return hare;
}

Complexity Analysis

Time Complexity: O(n) - where n is the length of the arraySpace Complexity: O(1) - only using two pointers

Pros and Cons

Pros:

Optimal time complexity
Constant space complexity
No modification to original array
Meets all problem constraints

Cons:

More complex to understand
Requires understanding of cycle detection concept

Code Solutions

Checking out 4 solutions in different languages for Find the Duplicate Number. Click on different languages to view the code.

class Solution {
public
  int findDuplicate(int[] nums) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      int cnt = 0;
      for (int v : nums) {
        if (v <= mid) {
          ++cnt;
        }
      }
      if (cnt > mid) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

Video Solution

Watch the video walkthrough for Find the Duplicate Number

Algorithms:

Binary Search

Patterns:

Two PointersBit Manipulation

Data Structures:

Array

Companies:

Goldman Sachs |Google |IBM |Infosys |