593. Straight Runs Split
A game deals out numbered tiles, and the integer nums[i] is the number on tile i. The tiles may come in any order and numbers may repeat. A straight run is a group of at least 3 tiles whose numbers are consecutive integers, such as 4, 5, 6 or 9, 10, 11, 12.
Decide whether it is possible to divide all the tiles into straight runs, with every tile used in exactly one run. Return true if such a division exists and false otherwise. Runs may overlap in the numbers they cover, as long as each physical tile is used once. Your solution should run in O(n log n) time with O(n) extra space.
Example 1
- Input:
- nums = [3,4,5,4,5,6]
- Output:
- true
- Explanation:
The tiles split into the runs 3,4,5 and 4,5,6, so the answer is true.
Example 2
- Input:
- nums = [1,2,3,3,4,5,6]
- Output:
- true
- Explanation:
Runs 1,2,3 and 3,4,5,6 use every tile, so the answer is true.
Example 3
- Input:
- nums = [1,2,3,3,4]
- Output:
- false
- Explanation:
The second 3 and the 4 can only form a run of length 2, so the tiles cannot all be used and the answer is false.
Constraints
1 ≤ nums.length ≤ 200000-109 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)