Compact Sorted Values

Practice Exercise Intermediate Medium Same-direction Pointers 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 compact_sorted_values(values). values is sorted. Return a new list containing one copy of each distinct value without using set or dict.

Starter code

def compact_sorted_values(values):
    pass

Test cases

repeated-runs

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

Expected: [1,2,4]

already-distinct

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

Expected: [1,3,5]

Wizard outline

Step 1: Establish the first write
Handle empty input and seed the first distinct value. The first item has no predecessor and defines the initial compact prefix.
Step 2: Advance the read pointer
Append the next distinct run with a separate read cursor. The first transition proves that sorted adjacency can advance the write frontier without copying duplicates.
Step 3: Preserve every distinct run
Complete the contract for long runs and already-distinct input. The same monotone read/write invariant covers every run length without extra state.

Footguns and prerequisites

Advancing the write pointer for duplicates leaves repeated values.
Reading from the output instead of the input can skip unseen values.
arrays strings two pointers sliding window

Reviewed references

Hello Interview — Two-Pointer Overview

Recommended approach and implementation

Scan left to right with a read index while the end of a separate result acts as the write frontier.

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

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