Pattern1 Practice5 Interview

Same-direction Pointers

GuideCode Labs

Advance read and write pointers in one direction for compaction, partitioning, or deduplication. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Same-direction Pointers when the prompt's constraints and required operations match this shape: Advance read and write pointers in one direction for compaction, partitioning, or deduplication.

On this page · Separate Read and Write Roles

Checking your account…

Separate Read and Write Roles

A read pointer inspects every input item; a write pointer marks the next position in the valid compacted output. They move in the same direction but answer different questions.

State the Compacted Prefix

Before processing read, the half-open prefix [0, write) contains exactly the accepted items from earlier input, in order. Writing only at write preserves values that the reader has not consumed.

Trace Read and Write Pointers

Reference

def compact_trace(values):
    trace = []
    write = 0
    for read, value in enumerate(values):
        if read == 0 or value != values[read - 1]:
            write += 1
        trace.append([read, write, value])
    return trace

Practice

Implement compact_trace(values). Return [read, write, value] after processing each value while compacting adjacent duplicates in sorted input.

def compact_trace(values):
    pass

Public tests

Trace the compacted prefix length

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

Advance Each Pointer Once

Read advances every iteration. Write advances only when the current value belongs in the result. This gives O(n) time and O(1) auxiliary space, while the suffix beyond the returned logical length is unspecified.

Compact Unique Values In Place

Reference

def compact_unique(values):
    write = 0
    for value in values:
        if write == 0 or values[write - 1] != value:
            values[write] = value
            write += 1
    return write

Practice

Implement compact_unique(values). Compact sorted values in place and return the new logical length.

def compact_unique(values):
    pass

Public tests

Preserve one copy in the prefix

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

Choose In Place or a New List

Use in-place read/write when mutation is allowed and stable compaction matters. Build a new list when preserving the caller’s container or maximizing clarity matters more than O(1) extra space.

Explain It in an Interview

Say: “Everything before write is the finalized compacted prefix; read examines the next source value. On acceptance I write then advance.” Clarify the returned logical length and whether elements after it matter.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Same-direction Pointers 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
Same-direction Pointers decision loop	`O(n)`	`O(n)`	Scan left to right with a read index while the end of a separate result acts as the write frontier.

Space

O(n) for the focused Compact Sorted Values implementation.

Assumptions

The output begins with the first run. Each later value is appended exactly when it starts a new sorted run, so every distinct value appears once and in order.
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 Same-direction Pointers invariant before coding and preserve it after every update, traversal step, or recursive return.
The prefix before write contains exactly the accepted items.
Write never advances beyond read.
Separate the read cursor from the next write position. Preserve this property after every transition.
Use sorted adjacency to recognize duplicates without hashing. Preserve this property after every transition.

When To Use Or Avoid Same-direction Pointers

Use It When

Use Same-direction Pointers when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
Use it when the prefix before write contains exactly the accepted items.

Choose Another Tool When

Avoid Same-direction Pointers 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 Compact Sorted Values before optimizing.

Avoid

def compact_sorted_values(values):
    pass

Use instead

def compact_sorted_values(values):
    if not values:
        return []
    compact = [values[0]]
    for read in range(1, len(values)):
        if values[read] != compact[-1]:
            compact.append(values[read])
    return compact

Where you will hit this: Compact Sorted Values(opens in a new tab)

Breaking the maintained state

Appends every scanned value and therefore preserves duplicates.

Prevent it: Use the public tests and preserve this state: The prefix before write contains exactly the accepted items.

Avoid

def compact_sorted_values(values):
    return list(values)

Use instead

def compact_sorted_values(values):
    if not values:
        return []
    compact = [values[0]]
    for read in range(1, len(values)):
        if values[read] != compact[-1]:
            compact.append(values[read])
    return compact

Where you will hit this: Compact Sorted Values(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 compact_sorted_values(values):
    return list(values)

Use instead

def compact_sorted_values(values):
    if not values:
        return []
    compact = [values[0]]
    for read in range(1, len(values)):
        if values[read] != compact[-1]:
            compact.append(values[read])
    return compact

Where you will hit this: Add Two Numbers(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
Hello Interview — Two-Pointer Overview(opens in a new tab)
hello-interview · checked 2026-07-12

Checking your account…