Split Array into Consecutive Subsequences
Medium · Arrays & Hashing · Array · Hash Table · Greedy · Heap (Priority Queue)
Problem
You are given an integer array nums sorted in non-decreasing order. Split it into one or more subsequences so that every element belongs to exactly one subsequence and each subsequence
- is a run of consecutive increasing integers (each element is exactly one more than the previous), and
- has length 3 or more.
Return true if such a split exists, and false otherwise.
Examples
Input: nums = [1,2,3,4,4,5,6] Output: true
Split into [1,2,3,4] and [4,5,6].
Input: nums = [5,6,6,7,7,8] Output: true
Split into [5,6,7] and [6,7,8].
Input: nums = [1,2,4,5,6] Output: false
1 and 2 cannot grow to length 3 because 3 is missing.
Constraints
- 1 <= len(nums) <= 10^4
- -1000 <= nums[i] <= 1000
- nums is sorted in non-decreasing order
Approaches
- Baseline: extend the shortest run with heaps — time O(n log n), space O(n)
Follow-up
If the minimum length were k instead of 3, the counting greedy would have to claim k numbers at once, O(n · k). The heap version handles any k by extending the shortest run; the use cases ask exactly that, and for the fewest runs when any length is allowed.
Related problems
Start free on Cariara · Coding problems · System design studio
