Cyclic Sort Pattern

When to use Cyclic Sort

• The array contains exactly n elements drawn from the range 1..n or 0..n-1 (with at most one duplicate or one missing).
• You need to find the missing, duplicate, or first-positive-missing number in O(1) extra space.
• Hash-set and counting-array approaches are disqualified by an explicit space constraint.
• The problem mentions that numbers correspond to indices, like `nums[i] = i + 1`.
• Sorting the array is sufficient to derive the answer in a single follow-up pass.

Template

function cyclicSort(nums) {
  let i = 0;
  while (i < nums.length) {
    const correctIndex = nums[i] - 1;
    if (nums[i] !== nums[correctIndex]) {
      [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
    } else {
      i++;
    }
  }
  return nums;
}

Common mistakes

• Incrementing `i` inside the swap branch, which skips over the value you just placed and leaves the new value unprocessed.
• Comparing `nums[i] === correctIndex` (an index-vs-value mix-up) instead of `nums[i] === nums[correctIndex]`.
• Using Cyclic Sort on input ranges that are not 1..n or 0..n-1, where the index mapping breaks down.
• Forgetting to guard against out-of-range values in First Missing Positive — values outside 1..n must be ignored, not placed.
• Returning the partially-sorted array from inside the swap loop before completing all placements.