EasyCyclic Sort

Set Mismatch

Explanation & Solution

Description

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers got duplicated and another number got missing.

You are given an integer array nums representing the data status of this set after the error. Find the number that occurs twice and the number that is missing, and return them as an array [duplicate, missing].

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

Output:[2, 3]

Explanation: 2 appears twice, 3 is missing.

Constraints

2 <= nums.length <= 10^4
1 <= nums[i] <= n

Approach

Cyclic Sort pattern

1. Phase 1 — Cyclic Sort to Place Numbers

For each i, compute j = nums[i] - 1 (correct index for value nums[i])
If nums[i] !== nums[j], swap the two elements
If nums[i] === nums[j], the value is either already correct or is a duplicate — advance i
After this phase, every position that can be correctly filled is filled

2. Phase 2 — Find the Mismatch

Scan the sorted array: index k should hold value k + 1
The first index k where nums[k] !== k + 1 reveals both answers:
nums[k] is the duplicate (it appears at nums[k] - 1 as expected AND at k)
k + 1 is the missing number (no element claimed this index)

3. One Mismatch is Guaranteed

Since exactly one number is duplicated and one is missing, there is always exactly one "corrupt" index

🧠 Key Insight

Cyclic sort cleanly separates the problem: after sorting, the duplicate occupies an index that already has the correct value, while the missing number has no index to claim

Time

O(n)linear sort plus a single scan

Space

O(1)in-place modification, no hash maps needed

Visualization

Input:

[1, 2, 2, 4]

—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone

8 steps

Solution Code

Find All Duplicates in an Array

First Missing Positive