Description
Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.
Example
Example 1:1
2
3
4
5
6Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5
Example 2:1
2
3
4
5
6Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5
Example 3:1
2Input: [1,2,3,4,4,5]
Output: False
Constraints:
- 1 <= nums.length <= 10000
Solution
I used a greedy algorithm.
leftis a hashmap, left[i] counts the number of i that I haven’t placed yet.
endis a hashmap, end[i] counts the number of consecutive subsequences that ends at number i
Then I tried to split the nums one by one.
If I could neither add a number to the end of a existing consecutive subsequence nor find two following number in the left, I returned False
Time: O(N)
1 | class Solution { |