Dashboard/Coding patterns/14. Cyclic Sort

CODING PATTERNS · LESSON 14 OF 28 · 20 MIN VIDEO · 6 PROBLEMS

Cyclic Sort

Module Progress (0 / 6 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (20 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Cyclic Sort — How the Pattern Works

Cyclic Sort is an in-place array indexing pattern for inputs whose elements come from a known bounded integer range such as [1, n] or [0, n]. Rather than comparing arbitrary element pairs, it maps each in-range value v directly to its deterministic target index (such as j = v - 1 or j = v) and swaps misplaced values into their home slots. Maintaining the invariant that every swap permanently places at least one element into its final index bounds total swaps to at most n, reducing O(n log n) comparison sorting or O(n) hash-set space to O(n) time and O(1) auxiliary space.

WHEN TO USE THIS PATTERN
  • The input is a mutable integer array of length n whose values are drawn from a contiguous [1, n] or [0, n] domain, possibly with missing, duplicate, or out-of-bounds entries.
  • The problem asks for missing numbers, duplicate values, corrupt pairs, or the smallest missing positive integer under strict O(n) time and O(1) auxiliary space constraints.
  • Each valid element v has a deterministic home index (j = v - 1 for 1-indexed ranges or j = v for 0-indexed ranges), enabling the input array itself to act as a direct-address presence table.
  • Elements belong to fixed index classes (such as even values at even indices and odd values at odd indices) where paired misfits can be resolved in-place via swaps.
COMMON INTERVIEW PITFALLS
  • Checking i != j instead of nums[i] != nums[j] before swapping: when duplicate values exist, comparing indices causes an infinite loop as two identical numbers swap endlessly.
  • Advancing pointer i unconditionally inside a for-loop after a swap: incrementing i immediately skips placing the newly swapped-in element now sitting at nums[i].
  • Confusing 0-indexed and 1-indexed target mappings or omitting bounds guards: [0, n] maps v to index v (skipping v == n), whereas [1, n] maps v to v - 1 and must check 0 <= j < n when arbitrary integers are allowed.
  • Omitting the post-scan fallback return: if every index i in 0..n - 1 already holds its expected value, the missing integer lies just past the array bounds (n for [0, n] or n + 1 for [1, n]).
Exact-Range Cyclic Sort (1 to n)Use when all values lie in [1, n] (including problems with duplicates like Corrupt Pair) to route each unique value v to index v - 1 in-place.
def cyclic_sort_1_to_n(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 nums
Bounded-Range Placement and Mismatch ScanUse when nums may contain negatives, zeros, or values exceeding n (e.g., First Missing Positive) so out-of-bounds values must be skipped before scanning for the first gap.
def first_missing_in_range(nums: list[int]) -> int:
    n, i = len(nums), 0
    while i < n:
        j = nums[i] - 1
        if 0 <= j < n and nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    for i, v in enumerate(nums):
        if v != i + 1:
            return i + 1
    return n + 1
🔒 PRO PROBLEMTarget: O(n) time · O(1) space

02. Missing Number

Pattern Trigger: a range with one gap → place home, then scan

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

The values are one to n. Where does the value five live?