← Create New Paste

Cyclic Sort: Finding the Missing and Duplicate Numbers in 1..n

3 views
"You are given an array of n integers where every value is between 1 and n. Some values appear twice and some are missing. Return them." This family of questions (Find All Duplicates, Find All Numbers Disappeared, First Missing Positive, Set Mismatch) shows up in phone screens because it has an obvious O(n) extra-space answer and a less obvious O(1) extra-space answer. Interviewers want to see whether you notice the hint hiding in the constraint. The hint: values are also valid indexes When every value v satisfies 1 <= v <= n, the value itself tells you where it "belongs": index v - 1. That turns the array into its own hash table. There are two common ways to use this. Technique 1: cyclic sort (swap into place) Walk through the array with index i. While nums[i] is not at its home position and the home position does not already hold the same value, swap nums[i] with nums[nums[i] - 1]. Only move i forward when no more swaps are possible. i = 0 while i < n: j = nums[i] - 1 if nums[i] != nums[j]: nums[i], nums[j] = nums[j], nums[i] else: i += 1 After this pass, every value that exists sits at its home index. A second pass finds every position k where nums[k] != k + 1: k + 1 is missing, and nums[k] is a duplicate. Why is it O(n) even though there is a while loop? Each swap puts at least one value in its final position, so there can be at most n swaps in total. Saying this out loud is the part many candidates skip, and interviewers often ask for it. Technique 2: sign marking If you are allowed to modify values but would rather not swap, mark visits by negating. For each value v, look at index |v| - 1. If the number there is already negative, v is a duplicate; otherwise negate it. At the end, any index k still holding a positive number means k + 1 never appeared. Remember to use abs() when reading values, because earlier steps may have flipped them. First Missing Positive, the hard cousin When the array can contain zeros, negatives and values larger than n, apply cyclic sort only to values in the range 1..n and ignore the rest. The first index k with nums[k] != k + 1 gives the answer k + 1; if every position is correct, the answer is n + 1. Edge cases to mention - Swapping a value with an identical value forever: the nums[i] != nums[j] check prevents the infinite loop. - Modifying the input: ask whether that is allowed. If not, say you would copy the array or fall back to a hash set. - Off-by-one: values are 1-based, indexes are 0-based. Write the mapping down before you code. How to talk through it in the interview Start with the hash-set solution and its complexity, then say: "The values fit in 1..n, so I can use the array itself as the set." That sentence shows the interviewer you read the constraints, which is often what the question is really testing. If you freeze while explaining the swap loop under pressure, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, so you can keep your reasoning clear while the interviewer watches you code.
Created Nov 17, 2026 05:33 Expires Nov 17, 2027 05:33