Cyclic Sort
curriculum problem — sort `nums` containing exactly the integers [1..n] in O(n) via in-place swap.
Easy
Time
O(n) Space O(1) 2 min read
cyclic-sort
Problem#
(curriculum problem.) Given an array containing the integers [1..n] in some order with no duplicates and no extras, sort it in place in O(n) time.
Examples#
[3, 1, 5, 4, 2]→[1, 2, 3, 4, 5]
Constraints#
1 <= n <= 10^5.
Approach#
For each i, swap nums[i] to its home position (nums[i] - 1) until nums[i] is already correct.
Solution#
void cyclicSort(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; ) { int target = nums[i] - 1; if (nums[i] != nums[target]) swap(nums[i], nums[target]); else ++i; }}func cyclicSort(nums []int) { n := len(nums) for i := 0; i < n; { target := nums[i] - 1 if nums[i] != nums[target] { nums[i], nums[target] = nums[target], nums[i] } else { i++ } }}from typing import List
class Solution: def cyclicSort(self, nums: List[int]) -> None: n = len(nums) i = 0 while i < n: target = nums[i] - 1 if nums[i] != nums[target]: nums[i], nums[target] = nums[target], nums[i] else: i += 1function cyclicSort(nums) { const n = nums.length; let i = 0; while (i < n) { const target = nums[i] - 1; if (nums[i] !== nums[target]) { [nums[i], nums[target]] = [nums[target], nums[i]]; } else { i++; } }}class Solution { public void cyclicSort(int[] nums) { int n = nums.length; int i = 0; while (i < n) { int target = nums[i] - 1; if (nums[i] != nums[target]) { int tmp = nums[i]; nums[i] = nums[target]; nums[target] = tmp; } else { i++; } } }}function cyclicSort(nums: number[]): void { const n = nums.length; let i = 0; while (i < n) { const target = nums[i] - 1; if (nums[i] !== nums[target]) { [nums[i], nums[target]] = [nums[target], nums[i]]; } else { i++; } }}Editorial#
Linear because each swap places exactly one number in its final slot — total swaps ≤ n. The nums[i] != nums[target] check guards against the (impossible here) duplicate case but doubles as a “done” check.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#