엔지니어 게시판
LeetCode 솔루션 분류

[8/19] 659. Split Array into Consecutive Subsequences

컨텐츠 정보

본문

659. Split Array into Consecutive Subsequences
Medium
3794734Add to ListShare

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 3 or more.

Return true if you can split nums according to the above conditions, or false otherwise.

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] <= 1000
  • nums is 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
전체 396 / 3 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 173 명
  • 오늘 방문자 5,042 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,048 명
알림 0