Find the Duplicate Number (Cycle Detection on Array Indices)

• Value-as-pointer – from index i, jump to index arr[i], treating each value as the next index.
• Cycle guarantee – since n+1 values map to n indices and one repeats, two indices point to the same position, forming a cycle.
• Floyd's algorithm – phase 1 finds the meeting point inside the cycle; phase 2 finds the cycle entry.
• O(n) time, O(1) space – no sorting, no hash set, no array modification.
• Constraint-dependent – the trick requires values in [1, n] so jumps never leave the array.

What is the problem?

Given an array of n+1 integers where each is between 1 and n inclusive, exactly one number is repeated (possibly more than once). Find the duplicate without modifying the array and using only constant extra space. In a banking context, a locker provisioning system at National Bank of India issued one reference number twice, and the audit tool must find it.

Why does the value-as-pointer trick work?

Every value is a valid index in the range [1, n]. Starting from index 0, follow the chain: go to index arr[0], then to index arr[arr[0]], and so on. Because one value repeats, two different indices point to the same target, creating a junction. Following the chain past that junction forms a cycle, and the junction point is the duplicate value.

How does Floyd's cycle detection solve it?

Phase 1: Start slow and fast at index 0. Slow takes one jump per step (slow = arr[slow]), fast takes two (fast = arr[arr[fast]]). They will meet inside the cycle.

Phase 2: Reset one pointer to index 0, keep the other at the meeting point. Advance both one step at a time. They converge at the cycle entry, which is the duplicate value.

package com.bank.service;

public class DuplicateLockerFinder {

    public static int findDuplicate(int[] lockers) {
        // Phase 1: find meeting point inside cycle
        int slow = lockers[0];
        int fast = lockers[lockers[0]];
        while (slow != fast) {
            slow = lockers[slow];
            fast = lockers[lockers[fast]];
        }

        // Phase 2: find cycle entry (the duplicate)
        slow = 0;
        while (slow != fast) {
            slow = lockers[slow];
            fast = lockers[fast];
        }
        return slow;
    }

    public static void main(String[] args) {
        int[] lockers = {1, 3, 4, 2, 2};
        int duplicate = findDuplicate(lockers);
        System.out.println("Duplicate locker number: " + duplicate);
    }
}

Duplicate locker number: 2

Why start from index 0?

Index 0 is never pointed to by any value (values are in [1, n]), so it acts as the "head" of the linked structure, guaranteed to be outside the cycle. This ensures phase 2 correctly finds the entry point.

What is the time and space complexity?

• Time: O(n) because Floyd's algorithm runs in linear time relative to the length of the sequence.
• Space: O(1) because only two pointer variables are used.

How do alternatives compare?

| Approach | Time | Space | Modifies Array |
|---|---|---|---|
| Floyd's cycle detection | O(n) | O(1) | No |
| Sorting | O(n log n) | O(1) or O(n) | Yes |
| HashSet | O(n) | O(n) | No |
| Binary search on range | O(n log n) | O(1) | No |

Floyd's is the only approach that is simultaneously O(n) time, O(1) space, and non-destructive.

What is the binary search alternative?

Binary search on the value range [1, n]: for the midpoint m, count how many values are <= m. If the count exceeds m, the duplicate is in [1, m]; otherwise it is in [m+1, n]. This is O(n log n) time and O(1) space, respecting the no-modification constraint but slower than Floyd's.

public static int findDuplicateBinarySearch(int[] nums) {
    int lo = 1, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        int count = 0;
        for (int num : nums) {
            if (num <= mid) count++;
        }
        if (count > mid) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

What are common mistakes?

The most common mistake is starting both pointers at the same index in phase 1. Slow should start at arr[0] (one jump) and fast at arr[arr[0]] (two jumps) so they are properly offset. Another mistake is not understanding that the trick requires values in [1, n]: if a value were 0 or greater than n, a jump could point outside the array.

What should a senior engineer know?

A senior engineer explains that this is the same convergence argument as finding the start of a linked list cycle, applied to array indices instead of list nodes. The key insight is that the value-range guarantee (all values in [1, n]) is what makes the pointer interpretation valid. Without that guarantee, a jump could point outside the array. The senior also notes that if the problem allowed multiple duplicates, Floyd's would not work because the cycle structure would be more complex.