Split Array into Consecutive Subsequences

Share

Given an integer array nums sorted in non-decreasing order, return true if it is possible to split nums into one or more subsequences such that each subsequence consists of consecutive integers and has a length of at least 3.

Example 1
Input: [1,2,3,3,4,5] → Output: true
Example 2
Input: [1,2,3,3,4,4,5,5] → Output: true

Solution Approach

Greedy with two frequency maps: freq (remaining count) and tail (count of subsequences ending at each value). For each num, prefer extending an existing subsequence ending at num-1; else start a new one (needs num+1 and num+2).

  • freq: count of each number.
  • tail: count of subsequences ending at each value.
  • For each num (in order): if freq[num]==0 skip.
  • If tail[num-1]>0: extend that subseq, tail[num-1]--, tail[num]++.
  • Else: start new with num, num+1, num+2 (check freq), tail[num+2]++.
  • If neither possible: return false.
Java
import java.util.*;

class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer,Integer> freq = new HashMap<>(), tail = new HashMap<>();
        for (int n : nums) freq.merge(n, 1, Integer::sum);
        for (int num : nums) {
            if (freq.getOrDefault(num, 0) == 0) continue;
            freq.merge(num, -1, Integer::sum);
            if (tail.getOrDefault(num-1, 0) > 0) {
                tail.merge(num-1, -1, Integer::sum);
                tail.merge(num, 1, Integer::sum);
            } else if (freq.getOrDefault(num+1, 0) > 0 && freq.getOrDefault(num+2, 0) > 0) {
                freq.merge(num+1, -1, Integer::sum);
                freq.merge(num+2, -1, Integer::sum);
                tail.merge(num+2, 1, Integer::sum);
            } else return false;
        }
        return true;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)