Skip to main content
DSA patterns

Find All Duplicates in an Array

mediumArrays and hashingCiscoDellIBM

Problem statement

You are given an integer array nums of length n. Every value in nums is between 1 and n, and each value appears either once or twice — never more. Return every value that appears exactly twice.

You must do this in O(n) time, and using only O(1) extra space — the array you return doesn't count against that limit, only whatever extra memory you use while computing it. The tight range of values (every value fits as an index into the array itself) is what makes the O(1) version possible, similar to spotting duplicate IDs in a fixed-size pool of ports or worker slots without allocating a second structure to track what you've seen.

Examples

Example 1

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

Output: [2,3]

Explanation: 2 and 3 each appear twice in the array; every other value appears once.

Example 2

Input: nums = [1,1,2]

Output: [1]

Explanation: 1 appears twice, at index 0 and index 1. 2 appears once.

Example 3

Input: nums = [1]

Output: []

Explanation: A single value can't repeat, so nothing is returned.

Hints

Hint 1: Every value in nums is between 1 and n, and nums has length n — that means every value can double as a valid index into nums itself (value - 1).

Approach

Optimal: Index sign-marking

Intuition

The hash set works, but it uses O(n) extra memory to remember what's been seen. Here's the trick that avoids it: every value in nums is between 1 and n, which means every value can point at a valid index in nums itself — value x points at index x - 1. Walk through the array once. For each value x you visit, go to index x - 1 and flip the sign of whatever is stored there to negative — that's how you mark "I've now seen the value x". If you ever visit index x - 1 and find it's already negative, that means some earlier value already marked it, so x itself is the duplicate. The array becomes its own hash set, with no extra structure needed.

Steps

  1. For each index i from left to right, compute index = abs(nums[i]) - 1 (using abs because nums[i] may already have been flipped negative by an earlier step).
  2. If nums[index] is already negative, abs(nums[i]) is a duplicate — add it to the result.
  3. Otherwise, negate nums[index] to mark that this value has now been seen.
  4. After the pass, optionally restore every value to positive, so the input array is left unchanged for the caller.
  5. Return the result.

Dry run

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

i nums[i] index = abs(nums[i])-1 nums[index] before action
0 4 3 7 (positive) negate → nums[3] = -7
1 3 2 2 (positive) negate → nums[2] = -2
2 -2 1 3 (positive) negate → nums[1] = -3
3 -7 6 3 (positive) negate → nums[6] = -3
4 8 7 1 (positive) negate → nums[7] = -1
5 2 1 -3 (negative) duplicate! append 2
6 -3 2 -2 (negative) duplicate! append 3
7 -1 0 4 (positive) negate → nums[0] = -4

result = [2, 3], in the same order as the expected output.

Edge cases: nums = [1] negates nums[0] on the only step and never revisits it, so the result stays empty. When a value's own index points at itself (like nums = [1, 1]), the first occurrence marks its own cell negative, and the second occurrence reads that same cell and correctly reports a duplicate.

Complexity

Time O(n) - one pass to mark values by flipping signs, and (if you restore the array) one more pass to flip everything back.

Space O(1) - extra — only the loop counters and the result list are used; the result isn't counted as extra space, and no second array or set is allocated.

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


if __name__ == "__main__":
    print(sorted(Solution().findDuplicates([4, 3, 2, 7, 8, 2, 3, 1])))  # [2, 3]
    print(sorted(Solution().findDuplicates([1, 1, 2])))                # [1]
    print(sorted(Solution().findDuplicates([1])))                      # []
RecapThe whole problem in a few lines, for the night before
  • Spot it: values are in the range 1 to n and some appear twice; find them without extra space
  • Idea: use the array itself as a marker: for each value v, flip the sign of nums[v-1]; if it is already negative, v is a duplicate
  • Cost: O(n) time, O(1) extra space
  • Trap: read the value with abs(), because earlier steps may have made it negative

Interview follow-ups

  • What if a value could appear three or more times, not just at most twice?

    The plain sign-flip trick breaks down, because it can't tell 'seen once' apart from 'seen twice or more' — both just look like 'negative'. One fix is to only report a value the first time you find its cell already negative, and skip reporting it on any further encounters; that needs one extra bit of state per index (for example, packing a second flag into the value, or using a value far below -n as a distinct 'already reported' marker), which is still O(1) extra space but more delicate to implement correctly. If you'd rather not reuse the array as a marker at all, falling back to a frequency count (a hash map from value to how many times it's appeared) handles any repeat count cleanly, at the cost of the O(n) space the optimal approach avoids.

  • What if nums must stay completely untouched — you're not allowed to mutate it even temporarily?

    Then the in-place sign trick is off the table, since it needs to write into nums as it goes (even though it restores the values afterward). The hash-set approach becomes the right choice: it never touches the input at all, at the cost of O(n) extra space instead of O(1). There's no way to get both true read-only access and O(1) extra space for this problem — you have to give up one or the other.

Frequently asked questions

The trick uses each value as an index into the very same array — value x becomes index x - 1. That only produces a valid index if every value is between 1 and n, where n is the array's length. If values could be arbitrarily large, negative, or outside that range, there would be no matching cell to flip, and you'd have to fall back to a real hash set.

Any time you're scanning a fixed-range pool — worker slots, ports, shard IDs — for values that show up more than once, this in-place marking trick avoids allocating a second structure the size of the pool. It's a good test of whether someone notices a value range constraint can replace a hash set entirely, not just a test of loops and sets.

Yes, temporarily — that's the trade-off for true O(1) extra space. The optimal solution here restores every value back to positive in a final pass, so by the time it returns, nums looks exactly as it did going in. If the caller can't tolerate even a temporary mutation (for example, another thread might read nums concurrently), you'd need the hash set approach instead and accept the O(n) space cost.

The sign trick as written would misbehave: the second occurrence flips the flag negative and gets correctly reported, but a third occurrence would find that same cell already negative and get reported again, producing a duplicate entry in the output for a value that only truly needs reporting once. The problem's guarantee that every value appears at most twice is what keeps this approach correct — see the first follow-up for how you'd adapt it otherwise.