Pattern1 Practice1 Interview

In-place Index Mapping

GuideCode Labs

Reuse array positions as state when values have a bounded relationship to valid indices. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider In-place Index Mapping when the prompt's constraints and required operations match this shape: Reuse array positions as state when values have a bounded relationship to valid indices.

On this page · Map Values to Their Home Index

Checking your account…

Map Values to Their Home Index

When valid values lie in 1 through n, value v has a natural home at index v minus one. Correct placement turns the array itself into a membership structure.

Swap Until the Current Position Settles

At each index, keep swapping its valid value toward home until the position is correct, invalid, or blocked by an equal duplicate. Incrementing too early leaves a displaced value unprocessed.

Trace Home-Index Placement

Reference

def placement_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 placement_trace(values). Values are in 1..n. Return the array after each swap that moves a value toward index value-1.

def placement_trace(values):
    pass

Public tests

Settle values or detect duplicates

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

Protect Duplicates and Invalid Values

Check the value range before computing or indexing its home. If the home already contains the same value, stop swapping to avoid an infinite duplicate cycle.

Find the First Missing Positive

Reference

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

Practice

Implement first_missing_positive(values). Return the smallest missing positive using in-place index mapping; mutation is allowed.

def first_missing_positive(values):
    pass

Public tests

Ignore invalid and duplicate values

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

Choose Index Mapping or a Hash Set

Use index mapping when the domain aligns with array indexes, mutation is allowed, and O(1) auxiliary space matters. A hash set is clearer when values are unbounded or input must remain unchanged.

Explain It in an Interview

Say: “Every valid value owns one home index. A swap permanently places at least one value or exposes another unprocessed value, so total swaps are O(n).” State mutation, invalid-value handling, duplicates, and the final mismatch scan.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the In-place Index Mapping invariant is independent of a minor Python release.

Verify in Python docs

Complexity & Invariants

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

Operation	Average	Worst	Interview note
In-place Index Mapping decision loop	`O(n)`	`O(n)`	A bounded 1..n value domain can map directly into n array positions without a dictionary key lookup. After reading a value v, result[v - 1] is true and every previously marked position stays true.

Space

O(n) for the focused Mark Seen Indices implementation.

Assumptions

Every valid value maps to one unique zero-based position, so marking that position records membership without losing earlier marks. Reading the completed boolean array therefore reports exactly the values that occurred.
The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

State the precise In-place Index Mapping invariant before coding and preserve it after every update, traversal step, or recursive return.
Each encoded slot has one documented meaning.
Original values remain recoverable whenever the contract requires restoration.
A bounded 1..n value domain can map directly into n array positions without a dictionary key lookup. Preserve this property after every transition.
After reading a value v, result[v - 1] is true and every previously marked position stays true. Preserve this property after every transition.

When To Use Or Avoid In-place Index Mapping

Use It When

Use In-place Index Mapping when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
Use it when each encoded slot has one documented meaning.

Choose Another Tool When

Avoid In-place Index Mapping 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 Mark Seen Indices before optimizing.

Avoid

def mark_seen_indices(values):
    pass

Use instead

def mark_seen_indices(values):
    seen = [False] * len(values)
    for value in values:
        seen[value - 1] = True
    return seen

Where you will hit this: Mark Seen Indices(opens in a new tab)

Breaking the maintained state

Toggles each mapped position, causing an even number of duplicate occurrences to look absent.

Prevent it: Use the public tests and preserve this state: Each encoded slot has one documented meaning.

Avoid

def mark_seen_indices(values):
    seen = [False] * len(values)
    for value in values:
        seen[value - 1] = not seen[value - 1]
    return seen

Use instead

def mark_seen_indices(values):
    seen = [False] * len(values)
    for value in values:
        seen[value - 1] = True
    return seen

Where you will hit this: Mark Seen Indices(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 mark_seen_indices(values):
    seen = [False] * len(values)
    for value in values:
        seen[value - 1] = not seen[value - 1]
    return seen

Use instead

def mark_seen_indices(values):
    seen = [False] * len(values)
    for value in values:
        seen[value - 1] = True
    return seen

Where you will hit this: Find All Duplicates in an Array(opens in a new tab)

Reviewed References

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

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…