Implementation - The Coder's Brain

Phase 1: The Representation Problem

Algorithm says: "Track which subsequences need which numbers"

Coder asks: "How do I REPRESENT subsequences in code?"

First Instinct (The Naive Coder)

"I'll create a Subsequence object!"

class Subsequence {
    List<Integer> numbers;

    void add(int x) { ... }
    boolean needsNext(int x) { ... }
    int length() { ... }
}

List<Subsequence> allSubsequences = new ArrayList<>();

Problem discovered immediately:

For each number x:
    - Search through allSubsequences
    - Find which ones end at x-1
    - Pick one to extend

→ O(n²) time! (n numbers × searching list)
→ Memory bloat! (storing entire chains)

---

Phase 2: The Minimalist Question

Coder realizes: "Wait, what do I ACTUALLY need to know?"

Let's trace what the algorithm asks at each step:

When processing number x:

Question 1: "Can I extend something?"
    → Need to know: "Does any subsequence end at x-1?"

Question 2: "Can I start new?"
    → Need to know: "Do x+1 and x+2 exist unused?"

That's IT!

Key insight:

"I don't need to know WHICH subsequence, or WHAT'S IN IT—I only need COUNTS!"

---

Phase 3: The Data Structure Selection

Concern 1: Tracking unused numbers

Question: "How many copies of each number remain?"

Options:

Option A: Keep the original array, mark used ones
    [1,2,3,3,4,5]
     ✓ ✓ ✓ ? ? ?
    → Hard to update, lots of scanning

Option B: Use a Counter/Frequency Map
    freq = {1:1, 2:1, 3:2, 4:1, 5:1}
    → O(1) lookup and update!

Choice: HashMap<Integer, Integer> freq

Why HashMap?

• Key = the number itself
• Value = how many copies remain
• Operations needed:
  • Check if available: freq.get(x) > 0
  • Use one: freq.put(x, freq.get(x) - 1)
  • Both O(1)!

---

Concern 2: Tracking incomplete subsequences

Question: "Which subsequences are waiting for their next number?"

Mental model:

Imagine subsequences as "hungry mouths" 🍔

[1,2] is waiting, mouth open for 3
[3,4] is waiting, mouth open for 5
[2,3,4,5,6] is waiting, mouth open for 7

How do I organize these mouths?

The breakthrough thought:

"I don't care WHO is waiting—I care WHAT they're waiting for!"

Reorganize by demand:

Instead of:
    Subsequence A needs 3
    Subsequence B needs 3
    Subsequence C needs 5

Think:
    Number 3 is needed by 2 subsequences
    Number 5 is needed by 1 subsequence

→ need = {3: 2, 5: 1}

Choice: HashMap<Integer, Integer> need

Why this structure?

• Key = the number that's needed
• Value = how many subsequences need it
• Operations needed:
  • Check demand: need.get(x) > 0
  • Satisfy one demand: need.put(x, need.get(x) - 1)
  • Create new demand: need.put(x+1, need.get(x+1) + 1)
  • All O(1)!

---

Phase 4: The State Machine (Coder's View)

The loop structure:

for each number x in sorted array:

    // STATE CHECK: Is x already consumed?
    if (freq[x] == 0) {
        skip  // Earlier decision already used this x
    }

    // DECISION TREE:

    // Branch 1: EXTEND path
    if (need[x] > 0) {
        // State transitions:
        freq[x]--         // consume from supply
        need[x]--         // satisfy one demand
        need[x+1]++       // create new demand
    }

    // Branch 2: START path
    else if (freq[x+1] > 0 AND freq[x+2] > 0) {
        // State transitions:
        freq[x]--         // consume starter
        freq[x+1]--       // consume middle
        freq[x+2]--       // consume ender
        need[x+3]++       // create demand for continuation
    }

    // Branch 3: FAIL path
    else {
        return "fail"
    }

---

Phase 5: Understanding need

What need Really Represents

need[7] = 3

Translation:
"Three subsequences have their LAST element at 6,
 and they're all expecting 7 to be their NEXT element"

Visual representation:

Subsequence A: [..., 5, 6, ?]  ─┐
Subsequence B: [..., 4, 5, 6, ?]  ├─→ All need 7 next
Subsequence C: [6, ?]          ─┘

need[7] = 3

Why This Structure Is Genius

Compare to alternative:

// Alternative: Track each subsequence explicitly
List<Subsequence> subs;
for (Subsequence sub : subs) {
    if (sub.lastElement() == x - 1) {
        sub.add(x);
        break;
    }
}
→ O(n) per number = O(n²) total

With need map:

if (need[x] > 0) {
    need[x]--;
    need[x+1]++;
}
→ O(1) per number = O(n) total

The abstraction:

• We collapse ALL subsequences ending at the same number
• We only track the COUNT, not the identity
• This works because we don't care WHICH subsequence extends—any will do!

---

Complete Java Implementation

public String canSplit(int[] nums) {
    // Build frequency map
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    // Track subsequences waiting for next number
    Map<Integer, Integer> need = new HashMap<>();

    for (int x : nums) {
        // Skip if already used
        if (freq.get(x) == 0) {
            continue;
        }

        // Option 1: EXTEND existing subsequence
        if (need.getOrDefault(x, 0) > 0) {
            freq.put(x, freq.get(x) - 1);
            need.put(x, need.get(x) - 1);
            need.put(x + 1, need.getOrDefault(x + 1, 0) + 1);
        }
        // Option 2: START new subsequence
        else if (freq.getOrDefault(x + 1, 0) > 0 &&
                 freq.getOrDefault(x + 2, 0) > 0) {
            freq.put(x, freq.get(x) - 1);
            freq.put(x + 1, freq.get(x + 1) - 1);
            freq.put(x + 2, freq.get(x + 2) - 1);
            need.put(x + 3, need.getOrDefault(x + 3, 0) + 1);
        }
        // Option 3: FAIL
        else {
            return "fail";
        }
    }

    return "pass";
}

Time & Space Complexity

• Time: O(n) - single pass through array
• Space: O(n) - two hashmaps

---

Mental Model: Reservation System

Think of need as a reservation system at a restaurant:

need[7] = 3  means:

"Three tables have ordered the next course,
 and they ALL want dish #7 next"

When x=7 arrives from the kitchen:

need[7]--     → Serve one table
need[8]++     → That table now wants dish #8

You don't track WHICH table—you track HOW MANY tables want each dish.