Split Array into Consecutive Subsequences
You are given an integer array nums that is sorted in non-decreasing order.
Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:
- Each subsequence is a consecutive increasing sequence (i.e., each integer is exactly one more than the previous integer).
- All subsequences have a length of
3or more.
Return true if you can split nums according to the above conditions, or false otherwise.
A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. That is, [1, 3, 5] is a subsequence of [1, 2, 3, 4, 5] while [1, 3, 2] is not.
Example 1
Input
nums = [1,2,3,3,4,5]Output
truenums can be split into the subsequences [1, 2, 3] and [3, 4, 5], both consecutive and of length at least 3.
Example 2
Input
nums = [1,2,3,3,4,4,5,5]Output
truenums can be split into the subsequences [1, 2, 3, 4, 5] and [3, 4, 5], both consecutive and of length at least 3.
Constraints
- 1 <= nums.length <= 10^4
- -1000 <= nums[i] <= 1000
- nums is sorted in non-decreasing order.
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.