LeetCode 솔루션 분류
[8/19] 659. Split Array into Consecutive Subsequences
본문
659. Split Array into Consecutive Subsequences
Medium
3794734Add to ListShareYou 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. (i.e., [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: true Explanation: nums can be split into the following subsequences: [1,2,3,3,4,5] --> 1, 2, 3 [1,2,3,3,4,5] --> 3, 4, 5
Example 2:
Input: nums = [1,2,3,3,4,4,5,5] Output: true Explanation: nums can be split into the following subsequences: [1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5 [1,2,3,3,4,4,5,5] --> 3, 4, 5
Example 3:
Input: nums = [1,2,3,4,4,5] Output: false Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.
Constraints:
1 <= nums.length <= 104-1000 <= nums[i] <= 1000numsis sorted in non-decreasing order.
Accepted
113,291
Submissions
224,396
관련자료
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
import collections
class Solution:
def isPossible(self, nums: List[int]) -> bool:
freq = collections.Counter(nums)
nxt = collections.defaultdict(int)
for num in nums:
if not freq[num]: continue
if nxt[num]:
nxt[num] -= 1
nxt[num+1] += 1
elif freq[num+1] and freq[num+2]:
freq[num+1] -= 1
freq[num+2] -= 1
nxt[num+3] += 1
else: return False
freq[num] -= 1
return True
