0 questions using this pattern
Place each number at its "correct" index when dealing with arrays containing numbers in the range [1, n] or [0, n-1].
Imagine a row of n chairs numbered 1 to n, and n people each holding a ticket with their seat number. Instead of searching for each person's seat, you ask everyone to swap positions until they're in their ticketed seat. After at most n swaps, everyone is seated correctly.
For an array where values should map directly to indices (e.g., value 3 belongs at index 2 if 1-indexed), repeatedly swap each element to its correct position until the array is "sorted."
Key insight: Each swap places at least one element correctly, so at most n swaps are needed -> O(n) time with O(1) space.
Use this skeleton as a starting point for problems using this pattern:
def cyclic_sort(nums: list[int]) -> list[int]:
"""Sort array where values are in range [1, n]."""
i = 0
while i < len(nums):
# Correct index for value nums[i] (1-indexed value -> 0-indexed position)
correct_idx = nums[i] - 1
# If not in correct position and not a duplicate, swap
if nums[i] != nums[correct_idx]:
nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
else:
i += 1
return nums
def find_missing(nums: list[int]) -> int:
"""Find missing number after cyclic sort."""
cyclic_sort(nums)
for i, num in enumerate(nums):
if num != i + 1:
return i + 1
return len(nums) + 1Look for these keywords and patterns in problem descriptions:
Swapping endlessly when current value equals value at target index (both are duplicates).
Fix:
Check nums[i] != nums[correct_idx] before swapping, not just
nums[i] != correct_idx + 1.
Confusing 0-indexed vs 1-indexed. If values are 1 to n, correct
index is value - 1. If values are 0 to n-1, correct index equals value.
Fix:
Clearly define the mapping: correct_idx = nums[i] - 1 for 1-indexed values.
After cyclic sort, scan for index where value != index + 1
Examples: missing-number
After cyclic sort, find where value != expected
Examples: find-the-duplicate-number
Ignore negatives and values > n, then cyclic sort
Examples: first-missing-positive
Collect all indices where value != expected
Examples: find-all-numbers-disappeared-in-an-array
Explore similar techniques:
Use two pointers moving at different speeds to detect cycles, find midpoints, or identify patterns in sequences. The fast pointer advances twice as quickly, allowing detection of structural properties without extra space.
Exploit bounded value ranges to achieve linear time sorting or selection by using values as array indices.