Split Array into Consecutive Subsequences

medium greedy hash map

Problem

Can the array be split into one or more subsequences of consecutive integers each of length ≥ 3?

Inputnums = [1,2,3,3,4,5]

OutputTrue

[1,2,3] and [3,4,5].

input

def is_possible(nums):
    from collections import Counter
    left = Counter(nums); ends = Counter()
    for x in nums:
        if left[x] == 0: continue
        left[x] -= 1
        if ends[x - 1] > 0: ends[x - 1] -= 1; ends[x] += 1
        elif left[x + 1] > 0 and left[x + 2] > 0:
            left[x + 1] -= 1; left[x + 2] -= 1; ends[x + 2] += 1
        else: return False
    return True

function isPossible(nums) {
  const left = new Map(), ends = new Map();
  const inc = (m, k, d=1) => m.set(k, (m.get(k)||0) + d);
  nums.forEach(x => inc(left, x));
  for (const x of nums) {
    if (!left.get(x)) continue;
    left.set(x, left.get(x) - 1);
    if (ends.get(x - 1) > 0) { ends.set(x - 1, ends.get(x - 1) - 1); inc(ends, x); }
    else if (left.get(x + 1) > 0 && left.get(x + 2) > 0) {
      left.set(x + 1, left.get(x + 1) - 1); left.set(x + 2, left.get(x + 2) - 1); inc(ends, x + 2);
    } else return false;
  }
  return true;
}

boolean isPossible(int[] nums) {
    Map left = new HashMap<>(), ends = new HashMap<>();
    for (int x : nums) left.merge(x, 1, Integer::sum);
    for (int x : nums) {
        if (left.getOrDefault(x, 0) == 0) continue;
        left.merge(x, -1, Integer::sum);
        if (ends.getOrDefault(x - 1, 0) > 0) { ends.merge(x - 1, -1, Integer::sum); ends.merge(x, 1, Integer::sum); }
        else if (left.getOrDefault(x + 1, 0) > 0 && left.getOrDefault(x + 2, 0) > 0) {
            left.merge(x + 1, -1, Integer::sum); left.merge(x + 2, -1, Integer::sum); ends.merge(x + 2, 1, Integer::sum);
        } else return false;
    }
    return true;
}

bool isPossible(vector& nums) {
    unordered_map left, ends;
    for (int x : nums) left[x]++;
    for (int x : nums) {
        if (left[x] == 0) continue;
        left[x]--;
        if (ends[x - 1] > 0) { ends[x - 1]--; ends[x]++; }
        else if (left[x + 1] > 0 && left[x + 2] > 0) { left[x + 1]--; left[x + 2]--; ends[x + 2]++; }
        else return false;
    }
    return true;
}

Explanation

We want to know if the sorted-ish array can be carved into runs of consecutive integers, each at least length 3. The greedy rule: when handling a number, prefer to extend an existing run that wants it; only start a new run if you cannot.

We use two hash counters. left tracks how many of each value are still unused, and ends tracks how many runs are currently waiting for a given value to continue (keyed by the run's last number).

For each value x (still available), we first check ends[x - 1]: if some run ended at x - 1, we append x to it, so that run now ends at x. Otherwise we try to start a fresh run x, x+1, x+2, consuming those from left. If neither is possible, the split fails and we return false.

Example: nums = [1,2,3,3,4,5]. The first 3 starts run [1,2,3] (recorded as ending at 3). The second 3 finds no run ending at 2, so it starts [3,4,5]. Everything is consumed → True.

Greedily extending before starting new runs guarantees we never strand a number that could have lengthened an existing run.

Time: O(n) Space: O(n)