Cyclic Sort and Index Placement

1. The unusually strong constraint

If an array of length n contains values 1..n, value x has exactly one natural home:

correctIndex(x) = x - 1

That mapping replaces comparison. Instead of asking which of two values is smaller, send each value directly to its home.

2. Template

int i = 0;
while (i < nums.size()) {
    int correct = nums[i] - 1;
    if (nums[i] != nums[correct])
        swap(nums[i], nums[correct]);
    else
        i++;
}

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

Do not increment i after a swap. A new, unchecked value just arrived at index i.

3. Invariant and complexity

Before advancing past index i, either:

• nums[i] === i + 1, so the value is home, or
• the correct home already contains the same value, proving a duplicate blocks placement.

Every successful swap puts at least one value home. At most n values can become newly placed, so all swaps total O(n). Space is O(1).

4. Variants

• Missing number in 0..n: adapt the home mapping to correctIndex(x)=x, skipping value n.
• Find all disappeared numbers: place what you can, then every index with nums[i] !== i+1 contributes missing value i+1.
• Find a duplicate: after placement, a blocked value is the duplicate.
• First missing positive: first partition away non-positive and too-large values, then place the remaining 1..n values.

5. When not to use it

• Values are arbitrary integers rather than a dense index range.
• Input must not be mutated.
• Relative order must be preserved.
• The range is far larger than array length.

Then use hashing, sorting, or another pattern. The constraint is what makes cyclic placement legal.

6. Traps

1. Incrementing after every swap and skipping the new arrival.
2. Failing to validate the destination range before indexing in a generalized variant.
3. Infinite loops on duplicates because equal destination values are swapped repeatedly.
4. Calling this ordinary comparison sorting. It only works because values encode their own homes.

7. Blank re-solve prompt

Sort a permutation of 1..n in place. Then modify the invariant for an array containing one duplicate and one missing value, without introducing a set.