Category: cyclic_sort
-
LeetCode 645: Set Mismatch
link Cyclic sort Cyclic sort to match nums with the reference sequence . The first mismatch is the answer. Time: , space: .
-
LeetCode 41: First Missing Positive
link Cyclic sort If nums only had positive numbers, we could cyclic sort it to match the sequence of positive integers and the first mismatch would have been the first missing positive number. To reduce the original problem to the above, simpler, all-positive case, we first sort around pivot 1. From the pivot index onwards,…
-
LeetCode 268: Missing Number
link Math Difference between expected sum and actual sum is the missing number. Time: , space: . Cyclic sort If we think about how nums would look like once sorted, there are two options: So, if we put each nums[i] in its expected index, there will be zero (first option) or one (second option) index…
unreasonably effective 