Skip to content
Hello Python
Pattern1 Practice1 Interview

Cyclic Sort

Place values into index-derived positions to find missing, duplicate, or misplaced elements in place. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Cyclic Sort when the prompt's constraints and required operations match this shape: Place values into index-derived positions to find missing, duplicate, or misplaced elements in place.

Pybit demonstrates the Cyclic Sort decision pattern in a professional coding interview workspace.
On this page · Give Each Value a Home Index

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Cyclic Sort Code Labs

Give Each Value a Home Index

When n values belong to 1 through n, value v owns index v minus one. Cyclic sort repeatedly places values into those natural positions.

Cycle Values into Place

At index i, swap the current value with the occupant of its home until i is correct or cannot progress. Do not advance i immediately after a swap because the new occupant is unprocessed.

Trace Cyclic Placements

Reference
def cyclic_trace(values):
    values=values.copy();trace=[];index=0
    while index<len(values):
        home=values[index]-1
        if values[index]!=values[home]:values[index],values[home]=values[home],values[index];trace.append(values.copy())
        else:index+=1
    return trace
Practice

Implement cyclic_trace(values). Values are 1..n; return the array after each swap toward home index value-1.

Public tests

  • Follow displaced values until settled

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Stop on Duplicate Occupancy

If a value’s home already contains the same value, the duplicate cannot be placed and another value is missing. Treat this as settled to avoid swapping equal values forever.

Find All Missing Values

Reference
def find_missing(values):
    values=values.copy();index=0
    while index<len(values):
        home=values[index]-1
        if values[index]!=values[home]:values[index],values[home]=values[home],values[index]
        else:index+=1
    return [index+1 for index,value in enumerate(values) if value!=index+1]
Practice

Implement find_missing(values). Values are in 1..n and may repeat; return absent values after cyclic placement.

Public tests

  • Treat duplicate occupancy as settled

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Cyclic Sort or Hashing

Choose cyclic sort when the value domain maps exactly to indexes, mutation is permitted, and O(1) auxiliary space matters. Choose hashing when values are unbounded or input must remain unchanged.

Explain It in an Interview

Say: “Each swap sends a value to its home or exposes another displaced value, so total swaps are O(n). Equal occupancy identifies a duplicate.” State domain validation, mutation, and how the final mismatch scan reveals missing values.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Cyclic Sort invariant is independent of a minor Python release.

Verify in Python docs(opens in a new tab)

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Cyclic Sort decision loopO(n)O(n)Cyclically place each in-range value on a copied list, then return the first index mismatch or n.

Space

O(n) for the focused Find a Missing Cyclic Value implementation.

Assumptions

  • Every present value below n is swapped into its unique matching index. Therefore a mismatched index is exactly the missing value; if none exists, the only unrepresented domain value is n.
  • The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

  1. State the precise Cyclic Sort invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Every settled in-range value occupies its matching index.
  3. Each swap settles at least one value or exposes a duplicate.
  4. Use value-as-index placement for a constrained domain. Preserve this property after every transition.
  5. Skip the sentinel value n that has no array slot. Preserve this property after every transition.

When To Use Or Avoid Cyclic Sort

Use It When

  • Use Cyclic Sort when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
  • Use it when every settled in-range value occupies its matching index.

Choose Another Tool When

  • Avoid Cyclic Sort when its decision rule cannot eliminate work or preserve the required state.
  • Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Find a Missing Cyclic Value before optimizing.

Avoid

def missing_value_cyclic(values):
    pass

Use instead

def missing_value_cyclic(values):
    arranged = list(values)
    index = 0
    while index < len(arranged):
        value = arranged[index]
        if value < len(arranged) and value != index:
            arranged[index], arranged[value] = arranged[value], arranged[index]
        else:
            index += 1
    for index, value in enumerate(arranged):
        if value != index:
            return index
    return len(arranged)

Where you will hit this: Find a Missing Cyclic Value(opens in a new tab)

Breaking the maintained state

Returns the displaced value instead of the mismatched index.

Prevent it: Use the public tests and preserve this state: Every settled in-range value occupies its matching index.

Avoid

def missing_value_cyclic(values):
    arranged=sorted(values)
    for i,v in enumerate(arranged):
        if i!=v: return v
    return len(arranged)

Use instead

def missing_value_cyclic(values):
    arranged = list(values)
    index = 0
    while index < len(arranged):
        value = arranged[index]
        if value < len(arranged) and value != index:
            arranged[index], arranged[value] = arranged[value], arranged[index]
        else:
            index += 1
    for index, value in enumerate(arranged):
        if value != index:
            return index
    return len(arranged)

Where you will hit this: Find a Missing Cyclic Value(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(n).

Avoid

def missing_value_cyclic(values):
    arranged=sorted(values)
    for i,v in enumerate(arranged):
        if i!=v: return v
    return len(arranged)

Use instead

def missing_value_cyclic(values):
    arranged = list(values)
    index = 0
    while index < len(arranged):
        value = arranged[index]
        if value < len(arranged) and value != index:
            arranged[index], arranged[value] = arranged[value], arranged[index]
        else:
            index += 1
    for index, value in enumerate(arranged):
        if value != index:
            return index
    return len(arranged)

Where you will hit this: First and Last Target Position(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.