Find All Duplicates in an Array — LC 442 In-Place Marking

Problem Statement#

Given nums of length n where every integer is in [1, n] and appears once or twice, return all integers that appear twice. Solve in O(n) time and O(1) extra space.

Constraints:

• 1 <= n <= 100000
• 1 <= nums[i] <= n
• Each element appears once or twice

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

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

Why This Problem Matters#

This is one of the most asked array interview questions at Amazon, Google, and Microsoft. It looks deceptively simple — until the interviewer says "do it without a hash set." That single constraint flips an O(n) hash lookup into a beautiful in-place trick.

The problem belongs to a family that includes LC 448 (Missing Number Range), LC 41 (First Missing Positive), and LC 287 (Find the Duplicate). Master one, you master all four. Recruiters know this — that is exactly why the index-negation trick keeps showing up in onsite loops.

The Core Insight#

Because every value is in [1, n], each nums[i] maps to a valid array index nums[i] - 1. That gives you a free presence map: visit a value, flip the sign of the slot it points to. The second time you visit, the slot is already negative — duplicate detected.

You only need abs(nums[i]) to read the original value, since the sign carries the visited bit. The array doubles as both data and metadata, and no auxiliary memory is required.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def findDuplicates(self, nums: list[int]) -> list[int]:
        result = []
        for x in nums:
            idx = abs(x) - 1
            if nums[idx] < 0:
                result.append(idx + 1)
            else:
                nums[idx] = -nums[idx]
        return result

var findDuplicates = function(nums) {
    const result = [];
    for (const x of nums) {
        const idx = Math.abs(x) - 1;
        if (nums[idx] < 0) {
            result.push(idx + 1);
        } else {
            nums[idx] = -nums[idx];
        }
    }
    return result;
};

Time: O(n) — single pass. Space: O(1) — output list excluded; we mutate the input.

Common Mistakes#

• Forgetting to take abs(x) after the first negation flips the sign.
• Off-by-one: the value is in [1, n], so the index is value - 1.
• Mutating the input without restoring it when the interviewer asks for purity.
• Pushing nums[idx] instead of idx + 1, which is wrong after negation.
• Trying to reset signs in a second pass and breaking the result list.

Interview Tips#

• Start with the hash-set solution to show you understand the problem.
• Then propose the negation trick and call out the [1, n] constraint as the trigger.
• If asked, mention you can restore the array with a second pass: nums[i] = abs(nums[i]).
• Explain why XOR or sum-based tricks fail when each value can repeat at most twice but you need every duplicate.

Follow-up Questions#

• LC 448 Find All Numbers Disappeared — flip same way, then collect positive indices.
• LC 287 Find the Duplicate Number — Floyd's cycle, since you cannot mutate.
• What if values are in [0, n-1]? Use +n modulo trick instead of negation.
• Can you find triplicates? Negation is a 1-bit marker; you would need two passes or modular arithmetic.
• Stream version with n unknown — fall back to hash set or Bloom filter.

Key Takeaways#

• LC 442 is solvable in O(n) time and O(1) extra space using sign flipping.
• Array values in [1, n] are always usable as indices into the same array.
• Use abs(nums[i]) to read the value while letting the sign track visits.
• Append idx + 1 to the output, not the negated array slot.
• The same trick generalizes to LC 41, 287, and 448.
• Always confirm with the interviewer whether mutating input is acceptable.
• A clean restore pass costs only O(n) and turns the algorithm pure.