The O(n) Club: Consecutive Subsequence Splitting—Java-Only, Tears Optional

The O(n) Club: Consecutive Subsequence Splitting—Java-Only, Tears Optional

⚡ TL;DR

Sorted array. Must split into consecutive chunks of 3+ (like [4,5,6]). Use each number once. Don’t settle for brute force unless your hobby is infinite timeouts. Try the greedy map method:

// Java way to survive the interview
boolean isPossible(int[] nums) {
    Map<integer integer> count = new HashMap<>();
    Map<integer integer> need = new HashMap<>();
    for (int num : nums) count.put(num, count.getOrDefault(num, 0) + 1);
    for (int num : nums) {
        if (count.get(num) == 0) continue;
        if (need.getOrDefault(num, 0) > 0) {
            need.put(num, need.get(num) - 1);
            need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
        } else if (count.getOrDefault(num + 1, 0) > 0 && count.getOrDefault(num + 2, 0) > 0) {
            count.put(num + 1, count.get(num + 1) - 1);
            count.put(num + 2, count.get(num + 2) - 1);
            need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
        } else {
            return false;
        }
        count.put(num, count.get(num) - 1);
    }
    return true;
}
</integer></integer>

🧠 How Devs Usually Mess This Up

If you’ve ever casually tossed pairs together, thinking “Hey, that’s consecutive!”, please pause and count past two—pairs are not valid, and your interviewer noticed before you finished the for-loop. Also, subsequences here do NOT mean overlaps, skips, or wild reuses. Every number gets a one-way ticket. And, hot tip: Greedily extending the longest existing sequence first? That’s how you strand sad, lonely 2-lengths at the end. Extend the shortest needy chain—don’t be a villain.

🔍 What’s Actually Going On

This is less like building a fence and more like playing Tetris with numbers—every block has one spot, and you lose the game if there’s an awkward gap (a group <3). Imagine each number is a domino: snap it onto an existing chain if someone’s waiting for it, or start a new chain if you can grab the next two. If you can't play it, sweep the board and go home.

🛠️ PseudoCode

• Count all frequencies:

  Map<integer> count = new HashMap<>();
  for (int num : nums) count.put(num, count.getOrDefault(num, 0) + 1);</integer>

  Track how many times each number shows up. One spreadsheet, no duplicates allowed on the dance floor.
• Track chain needs:

  Map<integer> need = new HashMap<>();</integer>

  Who in your lineup is desperately looking for a +1?
• For each number:
  • If there’s one left, see if someone’s begging for it (need.get(num) > 0):
    Attach it, decrement their need, and make them need num + 1 next.
  • Else, can you start a fresh chain? (count[num+1] && count[num+2]):
    Snag those two, and set up a thirst for num + 3.
  • Else, you lose—return false.
  • Always subtract one from count; don’t double-dip.
• Made it through? True! Every number joined one valid conga line.

💻 The Code

import java.util.HashMap;
import java.util.Map;
 public class SplitArrayGreedy {
    public boolean isPossible(int[] nums) {
        Map<integer integer> count = new HashMap<>();
        Map<integer integer> need = new HashMap<>();
        for (int num : nums) count.put(num, count.getOrDefault(num, 0) + 1);
        for (int num : nums) {
            if (count.get(num) == 0) continue;
            if (need.getOrDefault(num, 0) > 0) {
                need.put(num, need.get(num) - 1);
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            } else if (count.getOrDefault(num + 1, 0) > 0 && count.getOrDefault(num + 2, 0) > 0) {
                count.put(num + 1, count.get(num + 1) - 1);
                count.put(num + 2, count.get(num + 2) - 1);
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
            } else {
                return false;
            }
            count.put(num, count.get(num) - 1);
        }
        return true;
    }
}
</integer></integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Pairs are your enemy. [4,5] is tragic. Don’t let any group be shorter than 3.
• Duplicates? No problem—as long as you don’t reuse any number. Each spot is invite-only.
• Time: O(n). Space: O(n). Yes, the maps are chunky, but your stack won’t explode and your brain can relax.
• Don’t let a number join multiple chains. It’s one gig per DJ.

🧠 Interviewer Brain-Tattoo

“In code and in life, always extend the shortest needy chain—so you don’t get left holding the world’s saddest pair.”