EasyCyclic Sort

Cyclic Sort

Explanation & Solution

Description

Given an array nums of n distinct integers where each value is in the range [1, n], sort the array in-place using the cyclic sort algorithm and return it.

Cyclic sort works by iterating through the array and placing each element at its correct index (nums[i] - 1), swapping with the element currently at that position until every value is in place.

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

Output:[1, 2, 3, 4, 5]

Explanation: 3 belongs at index 2, 1 belongs at index 0, etc.

Constraints

n == nums.length
1 <= n <= 10^4
All integers in nums are distinct and in the range [1, n]

Approach

Cyclic Sort pattern

1. Understand the Key Invariant

For an array of n distinct integers in range [1, n], element with value v belongs at index v - 1
The goal is to place every element at its correct index in a single linear pass

2. Initialize the Loop

Start with i = 0
For each index i, compute the correct index for nums[i]: j = nums[i] - 1

3. Swap if Misplaced

If nums[i] !== nums[j] (the element is not at its correct index), swap nums[i] with nums[j]
Do not increment i yet — the newly swapped-in element might also need to be moved
This creates a "cycle" of swaps until the correct element lands at index i

4. Advance When Correct

If nums[i] === nums[j], the element is already in its correct position
Increment i to process the next index

5. Return the Sorted Array

After the loop completes, every element is at its correct index
The array is sorted in O(n) time with O(1) space

🧠 Key Insight

Cyclic sort is ideal when elements are in a known range [1, n]. It outperforms comparison-based sorts (O(n log n)) for this specific input constraint by exploiting index-value relationships

Time

O(n)each element is swapped at most once to its correct position

Space

O(1)sorting is done in-place with no extra data structures

Visualization

Input:

[3, 1, 5, 4, 2]

—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone

11 steps

Solution Code

Missing Number