05. Cyclic Sort#
Theory#
Use cyclic sort when an array of length n contains numbers in a known range (typically 1..n or 0..n) and you need O(n) time, O(1) extra space — often to find missing, duplicate, or first-missing-positive values.
Core idea: place each value v at index v - 1 (or v for 0-indexed ranges) by swapping until the current index is correct, then scan for anomalies.
def cyclic_sort(arr):
i = 0
while i < len(arr):
j = arr[i] - 1 # correct index for value arr[i] in range 1..n
if arr[i] != arr[j]:
arr[i], arr[j] = arr[j], arr[i]
else:
i += 1
Problems at a glance#
| LC | Problem | |
|---|---|---|
| 268 | Missing Number | ↗ |
| 442 | Find All Duplicates in an Array | ↗ |
| 448 | Find All Numbers Disappeared in an Array | ↗ |
| 645 | Set Mismatch | ↗ |
| 41 | First Missing Positive | ↗ |
Problems#
Problem 1: Missing Number (Leetcode:268)#
Problem Statement
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example 1:
Input: nums = [3,0,1] Output: 2
Constraints:
n == nums.length,1 <= n <= 10^4,0 <= nums[i] <= n, all unique.
Code and Explanation
class Solution:
def missingNumber(self, nums: list[int]) -> int:
ans = len(nums)
for i, x in enumerate(nums):
ans ^= i ^ x
return ans
XOR every index 0..n with every value. Pairs (i, nums[i]) for present numbers cancel out; only the missing value remains XOR'd with its index.
Time: O(n) · Space: O(1)
class Solution:
def missingNumber(self, nums: list[int]) -> int:
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
Expected sum of 0..n minus actual sum. Watch for integer overflow in other languages; Python handles big ints fine.
Time: O(n) · Space: O(1)
class Solution:
def missingNumber(self, nums: list[int]) -> int:
i = 0
while i < len(nums):
j = nums[i]
if nums[i] < len(nums) and nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
for i, x in enumerate(nums):
if x != i:
return i
return len(nums)
Place value v at index v when v < n. After sorting, the first index where nums[i] != i is the missing number; if all match, missing is n.
Time: O(n) · Space: O(1)
Problem 2: Find All Duplicates in an Array (Leetcode:442)#
Problem Statement
Given an integer array nums of length n where all integers are in [1, n] and each appears at most twice, return all integers that appear twice. O(n) time, O(1) extra space (output excluded).
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]
Code and Explanation
class Solution:
def findDuplicates(self, nums: list[int]) -> list[int]:
res = []
for x in nums:
idx = abs(x) - 1
if nums[idx] < 0:
res.append(abs(x))
else:
nums[idx] = -nums[idx]
return res
Use the sign of nums[x-1] as a visited flag. First time we see value x, negate nums[x-1]. Second time, nums[x-1] is already negative → x is a duplicate.
Time: O(n) · Space: O(1)
class Solution:
def findDuplicates(self, nums: list[int]) -> list[int]:
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
return [i + 1 for i, x in enumerate(nums) if x != i + 1]
Swap each value to its correct index. After placement, any index i where nums[i] != i + 1 holds a duplicate (the value that couldn't be placed uniquely).
Time: O(n) · Space: O(1)
Problem 3: Find All Numbers Disappeared in an Array (Leetcode:448)#
Problem Statement
Given nums of length n with values in [1, n], return all integers in [1, n] that do not appear.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1] Output: [5,6]
Code and Explanation
class Solution:
def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
for x in nums:
idx = abs(x) - 1
nums[idx] = -abs(nums[idx])
return [i + 1 for i, x in enumerate(nums) if x > 0]
Same marking trick as LC 442: negate nums[x-1] when we see x. Positive entries after the pass mean index i+1 never appeared.
Time: O(n) · Space: O(1)
class Solution:
def findDisappearedNumbers(self, nums: list[int]) -> list[int]:
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
return [i + 1 for i, x in enumerate(nums) if x != i + 1]
After cyclic sort, empty slots (wrong values) correspond to missing numbers i+1.
Time: O(n) · Space: O(1)
Problem 4: Set Mismatch (Leetcode:645)#
Problem Statement
One number from 1..n was duplicated and another is missing. Return [duplicate, missing].
Example 1:
Input: nums = [1,2,2,4] Output: [2,3]
Code and Explanation
class Solution:
def findErrorNums(self, nums: list[int]) -> list[int]:
dup = miss = 0
for x in nums:
idx = abs(x) - 1
if nums[idx] < 0:
dup = abs(x)
else:
nums[idx] = -nums[idx]
for i, x in enumerate(nums):
if x > 0:
miss = i + 1
return [dup, miss]
Second visit to an index reveals the duplicate; the index that stays positive is the missing number.
Time: O(n) · Space: O(1)
class Solution:
def findErrorNums(self, nums: list[int]) -> list[int]:
n = len(nums)
s = n * (n + 1) // 2
sq = n * (n + 1) * (2 * n + 1) // 6
diff = sum(nums) - s
diff_sq = sum(x * x for x in nums) - sq
# dup - miss = diff, dup + miss = diff_sq / diff
miss = (diff_sq // diff - diff) // 2
dup = diff + miss
return [dup, miss]
Compare actual sum and sum-of-squares to expected. Solve two equations for duplicate and missing. Works but less intuitive in interviews than marking.
Time: O(n) · Space: O(1)
Problem 5: First Missing Positive (Leetcode:41)#
Problem Statement
Return the smallest positive integer not in nums. O(n) time, O(1) extra space.
Example 1:
Input: nums = [3,4,-1,1] Output: 2
Code and Explanation
class Solution:
def firstMissingPositive(self, nums: list[int]) -> int:
n = len(nums)
i = 0
while i < n:
j = nums[i] - 1
if 1 <= nums[i] <= n and nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
Only values in [1, n] can be the answer. Place each valid value v at index v-1 (ignore negatives and values > n). Scan for first i where nums[i] != i+1; if all match, answer is n+1.
Time: O(n) · Space: O(1)
class Solution:
def firstMissingPositive(self, nums: list[int]) -> int:
n = len(nums)
if 1 not in nums:
return 1
if n == 1:
return 2
for i in range(n):
if nums[i] <= 0 or nums[i] > n:
nums[i] = 1
for x in nums:
idx = abs(x) - 1
nums[idx] = -abs(nums[idx])
for i in range(n):
if nums[i] > 0:
return i + 1
return n + 1
Normalize out-of-range values to 1, then use index marking like LC 448. First positive index → missing positive is i+1.
Time: O(n) · Space: O(1)