Split into runs of three
Decide whether a sorted list can be split into runs of consecutive numbers each at least three long, by extending the most recent run when you can and starting a new one only when you must. About 25 minutes.
Extend before you start
You get numbers sorted in non-decreasing order and must split them into groups, where each group is a run of consecutive numbers such as 3, 4, 5, with at least three numbers.
Take each number in turn. If some run is waiting for exactly this number as its next one, add it there. Extending a run never hurts: a run that is already three long needs nothing more, but a fresh start would require two more numbers later.
Start a new run or fail
If no run wants this number, it must begin a new run, so the next two numbers, one and two higher, must still be available. Use them up and record that a run now wants the number three higher.
If they are not available, the split is impossible and the answer is false. If every number is placed, the answer is true. A table of counts and a table of runs waiting give constant time per number.
need[x] -= 1 need[x + 1] += 1 # a run needs x + 1
2 has no waiting run. Start one: 2, 3, 4 uses the next two numbers. A run now waits for 5.
Numbers 1, 2, 3, 4, 4, 5. Can they be split into runs of three or more?
- ANo
- BYes
- COnly if the runs are of exactly three
Show the answer
No. One run is 1, 2, 3, 4, 5 and a lone 4 cannot start a run of three.
Split into runs of three
Given an integer array nums sorted in non-decreasing order, return true if you can split it into one or more subsequences so that every subsequence is a run of consecutive integers increasing by exactly 1, and has length at least 3. Each number must be used exactly once.
nums = [1, 2, 3, 3, 4, 5] → true
1 ≤ nums.length ≤ 10,000 · -1,000 ≤ nums[i] ≤ 1,000 · sorted in non-decreasing order