Find a Missing Cyclic Value

Practice Exercise Intermediate Medium Cyclic Sort Array

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement missing_value_cyclic(values). values contains n distinct integers chosen from 0 through n, so exactly one value is missing. Return the missing value without mutating values.

Starter code

def missing_value_cyclic(values):
    pass

Test cases

middle-missing

{
  "args": [
    [
      3,
      0,
      1
    ]
  ]
}

Expected: 2

sentinel-missing

{
  "args": [
    [
      0,
      1,
      2
    ]
  ]
}

Expected: 3

Wizard outline

Step 1: Place values around index zero
Recognize a missing zero after safe cyclic placement. The first array position gives a narrow observable placement invariant before general mismatch recovery.
Step 2: Read the first mismatch
Return any in-array index whose matching value never arrived. All present in-range values occupy their own positions after cyclic placement; missing n remains a separate final case.
Step 3: Handle missing n
Return n when every array index is correctly occupied. The only domain value without a physical slot is n itself.

Footguns and prerequisites

Trying to place n indexes past the array.
Failing to copy the list mutates caller-owned input.
arrays strings two pointers sliding window

Reviewed references

Python More on Lists

Recommended approach and implementation

Cyclically place each in-range value on a copied list, then return the first index mismatch or n.

Why it works: 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.

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)