Skip to main content

Complete Trace Example

Tracing [1,2,3,3,4,5]​

Let's trace through the algorithm step by step with full state visualization.

Initial State​

Array: [1,2,3,3,4,5]

freq = {1:1, 2:1, 3:2, 4:1, 5:1}
need = {}

Process x=1​

Check:

  • freq[1] = 1 (available) ✓
  • need[1] = 0 (no demand)
  • Can start? Check freq[2] and freq[3]
    • freq[2] = 1 ✓
    • freq[3] = 2 ✓

Action: START new subsequence [1,2,3,?]

State changes:

freq[1]--  →  freq = {1:0, 2:0, 3:1, 4:1, 5:1}
freq[2]--
freq[3]--
need[4]++  →  need = {4:1}

Mental model:

Active chains:
[1,2,3,?] needs 4

Process x=2​

Check:

  • freq[2] = 0 (already used)

Action: SKIP

Process x=3 (first one)​

Check:

  • freq[3] = 1 (available) ✓
  • need[3] = 0 (no demand)
  • Can start? Check freq[4] and freq[5]
    • freq[4] = 1 ✓
    • freq[5] = 1 ✓

Action: START new subsequence [3,4,5,?]

State changes:

freq[3]--  →  freq = {1:0, 2:0, 3:0, 4:0, 5:0}
freq[4]--
freq[5]--
need[6]++  →  need = {4:1, 6:1}

Mental model:

Active chains:
[1,2,3,?]   needs 4
[3,4,5,?]   needs 6

Process x=3 (second one)​

Check:

  • freq[3] = 0 (already used)

Action: SKIP

Process x=4​

Check:

  • freq[4] = 0 (already used)

Action: SKIP

Process x=5​

Check:

  • freq[5] = 0 (already used)

Action: SKIP

Final State​

freq = {1:0, 2:0, 3:0, 4:0, 5:0}  (all consumed ✓)
need = {4:1, 6:1}  (chains waiting, but we're done)

Result: "pass"

Final chains:

[1,2,3]  (length 3 ✓)
[3,4,5]  (length 3 ✓)

Why This Works​

Key Observations​

  1. All numbers consumed: freq shows all 0s
  2. Remaining demand is OK: Chains in need are already length ≥ 3
  3. Greedy worked: By starting chains as soon as possible, we successfully allocated all numbers

The Invariant​

At any point during processing:

Every number is either:
1. Still in freq (unused)
2. Part of a valid chain (length ≥ 3)
3. Part of a growing chain (will reach length 3)

Example That Fails​

Let's trace [1,2,3,4,4,5]:

Initial State​

freq = {1:1, 2:1, 3:1, 4:2, 5:1}
need = {}

Process x=1​

Action: START [1,2,3,?]

freq = {1:0, 2:0, 3:0, 4:2, 5:1}
need = {4:1}

Process x=2, x=3​

Action: SKIP (already used)

Process x=4 (first one)​

Check:

  • freq[4] = 2 ✓
  • need[4] = 1 ✓ (chain [1,2,3] needs 4!)

Action: EXTEND [1,2,3] → [1,2,3,4,?]

freq = {1:0, 2:0, 3:0, 4:1, 5:1}
need = {4:0, 5:1}

Process x=4 (second one)​

Check:

  • freq[4] = 1 ✓
  • need[4] = 0 (no demand)
  • Can start? Need freq[5] and freq[6]
    • freq[5] = 1 ✓
    • freq[6] = 0 ✗ (doesn't exist!)

Action: FAIL

Can't extend (no demand)
Can't start (missing 6)
Return "fail"

Why it fails: The second 4 can't form a valid subsequence because 6 doesn't exist.

Practice: Trace This Yourself​

Try tracing [1,2,3,4,5,6,7,8]:

Click to see answer

Process x=1: START [1,2,3,?]

freq = {1:0, 2:0, 3:0, 4:1, 5:1, 6:1, 7:1, 8:1}
need = {4:1}

Process x=4: EXTEND [1,2,3] → [1,2,3,4,?]

freq = {1:0, 2:0, 3:0, 4:0, 5:1, 6:1, 7:1, 8:1}
need = {5:1}

Process x=5: EXTEND → [1,2,3,4,5,?]

need = {6:1}

Process x=6: EXTEND → [1,2,3,4,5,6,?]

need = {7:1}

Process x=7: EXTEND → [1,2,3,4,5,6,7,?]

need = {8:1}

Process x=8: EXTEND → [1,2,3,4,5,6,7,8,?]

need = {9:1}

Result: "pass" (one long chain of length 8)