Set Mismatch

Set Mismatch hands you a shuffled set that should have been 1, 2, ..., n, but one number got copied over another. One value now appears twice and one value has vanished. Your job is to name both. The slick trick: the values are their own addresses, so we can sort them into place by swapping and let the array tell us what went wrong.

The slow way first

The plain approach: count how many times each value shows up. Tally every number with a hash map or a size-n counter array, then scan the counts — the value with count 2 is the duplicate, the value with count 0 is missing. That works and it is O(n) time, but it spends O(n) extra space on the counter.

The question to ask: the values are exactly 1..n, so each value already knows where it belongs. Can I use the array itself as the bookkeeping and avoid the extra space? Yes — by sorting the values into their home slots in place.

The idea: send each value to its home slot

Value v belongs at index v - 1. Walk i across the array and repeatedly swap nums[i] toward its home until i holds a value that is already home. When you try to place a value but its home slot already holds that same value, the swap would change nothing — that is the duplicate, with no slot left for it. Stop swapping and move on.

After placement, every value that has a home is sitting at its index. Exactly one index is wrong: it holds a repeated value instead of the one that should live there. That index i gives both answers at once — nums[i] is the duplicate and i + 1 is the missing number.

Walk through it

Step through the animation. The i pointer scans left, and the slot marker shows where each value wants to go. The 1s, 2, and 4 are already home, so they lock in fast. When i reaches the second 2, its home slot already holds a 2 — the swap is a no-op, so that cell is stuck and flagged. The final scan finds index 2 holding 2 when it should hold 3, giving [2, 3].

Pseudocode

i = 0
while i < n:
    slot = nums[i] - 1                 # where value nums[i] belongs
    if nums[i] != nums[slot]:
        swap nums[i] and nums[slot]    # send this value home
    else:
        i += 1                         # already home (or a no-op duplicate)
for i from 0 to n - 1:
    if nums[i] != i + 1:               # the one wrong slot
        return [nums[i], i + 1]        # [duplicate, missing]
return []

The Python solution

def find_error_nums(nums):
    i = 0
    while i < len(nums):
        slot = nums[i] - 1
        if nums[i] != nums[slot]:
            nums[i], nums[slot] = nums[slot], nums[i]
        else:
            i += 1
    for i in range(len(nums)):
        if nums[i] != i + 1:
            return [nums[i], i + 1]
    return []

• slot = nums[i] - 1 is the home index for the value currently at i.
• Line 5 asks whether that home slot already holds this value. If not, line 6 swaps the value into place — and crucially we do not advance i, because a new value just arrived at i and might also need placing.
• If the home slot already holds the same value, the swap would be a no-op, so we take the else and advance i. That no-op case is exactly the duplicate that has nowhere to go.
• The final loop is the payoff: the single index where nums[i] != i + 1 gives the duplicate nums[i] and the missing value i + 1.

Complexity

The placement loop looks like a while with a nested swap, but each swap lands a value in its final home, so there are at most n swaps total — still O(n). The win is space: we sort in place and use only a couple of index variables, so it is O(1) extra.

When this pattern shows up

Practice