Intervals - Split Array into Consecutive Subsequences

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.

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

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

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.

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)