Find the Duplicate Number

Problem Statement

Given an array nums containing n + 1 integers where:

• Each integer is in the range [1, n]
• There is only one repeated number
• Return that duplicate number

Example

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

---

Brute Force Approach

Interview Explanation

The most straightforward solution is to compare every element with every other element. If two numbers are equal, we have found the duplicate.

Since we check all possible pairs, the duplicate is guaranteed to be found.

Time & Space Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Java Code

class Solution {
    public int findDuplicate(int[] nums) {

        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] == nums[j]) {
                    return nums[i];
                }
            }
        }

        return -1;
    }
}

---

Better Approach – HashSet

Interview Explanation

Instead of repeatedly searching for duplicates, we can store already seen numbers inside a HashSet.

Before inserting a number, check whether it already exists in the set.

If it does, that's our duplicate.

Why HashSet?

HashSet provides nearly O(1) lookup time, eliminating the need for nested loops.

Time & Space Complexity

• Time Complexity: O(N)
• Space Complexity: O(N)

Java Code

class Solution {
    public int findDuplicate(int[] nums) {

        HashSet<Integer> seen = new HashSet<>();

        for(int num : nums) {
            if(seen.contains(num)) {
                return num;
            }

            seen.add(num);
        }

        return -1;
    }
}

---

Optimal Approach – Floyd's Cycle Detection

Most interviewers won't stop at HashSet.

They'll ask:

Can you solve it in O(1) extra space?

This is where the real trick begins.

---

Observation

Every number in the array lies between 1 and n.

Think of each value as a pointer to the next index.

index -> nums[index]

For:

nums = [1,3,4,2,2]

we get:

0 -> 1
1 -> 3
3 -> 2
2 -> 4
4 -> 2

Visualized:

0 → 1 → 3 → 2 → 4
          ↑     ↓
          ← ← ←

A cycle appears.

And what creates this cycle?

The duplicate number.

This transforms the problem into:

Find the starting point of the cycle in a linked list.

Exactly what Floyd's Algorithm does.

---

Phase 1: Detect the Cycle

Use two pointers:

• Slow moves one step
• Fast moves two steps

slow = nums[slow];
fast = nums[nums[fast]];

Eventually they meet inside the cycle.

---

Phase 2: Find the Duplicate

Move one pointer back to the beginning.

Now move both one step at a time.

Where they meet again is the duplicate number.

---

Dry Run

Input

nums = [1,3,4,2,2]

Initial State

slow = 1
fast = 1

Iteration 1

slow = nums[1] = 3

fast = nums[nums[1]]
     = nums[3]
     = 2

Iteration 2

slow = nums[3] = 2

fast = nums[nums[2]]
     = nums[4]
     = 2

Pointers meet at:

2

Cycle detected.

---

Reset Slow

slow = nums[0]

Move both one step at a time:

slow = nums[slow]
fast = nums[fast]

They meet again at:

2

This is the duplicate number.

---

Optimal Java Solution

class Solution {
    public int findDuplicate(int[] nums) {

        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];

        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
}

---

Complexity Analysis

Time Complexity

• Phase 1: O(N)
• Phase 2: O(N)

Overall:

O(N)

Space Complexity

O(1)

No extra data structures are used.

---

Interview Takeaway

Whenever you see:

• Array values limited to a range
• Numbers acting like references
• Need to find duplicates
• O(1) space requirement

Think:

Index = Node
Value = Next Pointer

The moment you see that transformation, the problem becomes:

Find the entrance of a cycle in a linked list.

And Floyd's Tortoise and Hare algorithm solves it beautifully.

GitHub: https://github.com/codewithjaspreet

LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/

Medium: https://medium.com/@jaspreet.dev