How to Find Duplicate Numbers in an Array in O(n) Time and O(1) Space

Given an array nums of length n where each element is in the range 0 … n‑1, the task is to return any number that appears more than once, without knowing how many duplicates exist.

Approach 1 – HashSet

Idea: Insert each element into a HashSet. Because a set cannot contain duplicates, the insertion fails (or the element is already present) exactly when a duplicate is encountered.

When add(num) returns false (or contains(num) is true), return num as the repeated value.

Time complexity: O(n). Space complexity: O(n) for the auxiliary set.

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums) {
            if (!numsSet.add(num)) {
                return num;
            }
        }
        return -1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    const numsSet = new Set();
    for (const num of nums) {
        if (numsSet.has(num)) {
            return num;
        } else {
            numsSet.add(num);
        }
    }
    return -1;
};

Approach 2 – In‑Place Swapping (Array as Hash)

Observation: Because values are bounded by the index range, each number ideally belongs at the index equal to its value.

Algorithm: Iterate over the array; while the current element nums[i] is not at its correct position ( nums[i] != i), swap it with the element at its target index nums[nums[i]]. If during this process we find that nums[i] == nums[nums[i]], a duplicate has been found and is returned.

The while loop ensures that after each swap the newly placed element is also examined, guaranteeing all positions are eventually correct or a duplicate is detected.

Time complexity: O(n). Space complexity: O(1) because no extra data structures are allocated.

class Solution {
    public int findRepeatNumber(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) {
                return nums[i];
            }
            const temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
    }
    return -1;
};

The accompanying diagrams (shown below) illustrate how the in‑place swapping gradually moves each element to its rightful index and where the duplicate detection occurs.