Welcome to Subscribe On Youtube

659. Split Array into Consecutive Subsequences

Description

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.

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] <= 1000
  • nums is sorted in non-decreasing order.

Solutions

  • class Solution { public boolean isPossible(int[] nums) { Map<Integer, PriorityQueue<Integer>> d = new HashMap<>(); for (int v : nums) { if (d.containsKey(v - 1)) { var q = d.get(v - 1); d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(q.poll() + 1); if (q.isEmpty()) { d.remove(v - 1); } } else { d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(1); } } for (var v : d.values()) { if (v.peek() < 3) { return false; } } return true; } } 
  • class Solution { public: bool isPossible(vector<int>& nums) { unordered_map<int, priority_queue<int, vector<int>, greater<int>>> d; for (int v : nums) { if (d.count(v - 1)) { auto& q = d[v - 1]; d[v].push(q.top() + 1); q.pop(); if (q.empty()) { d.erase(v - 1); } } else { d[v].push(1); } } for (auto& [_, v] : d) { if (v.top() < 3) { return false; } } return true; } }; 
  • class Solution: def isPossible(self, nums: List[int]) -> bool: d = defaultdict(list) for v in nums: if h := d[v - 1]: heappush(d[v], heappop(h) + 1) else: heappush(d[v], 1) return all(not v or v and v[0] > 2 for v in d.values()) 
  • func isPossible(nums []int) bool { d := map[int]*hp{} for _, v := range nums { if d[v] == nil { d[v] = new(hp) } if h := d[v-1]; h != nil { heap.Push(d[v], heap.Pop(h).(int)+1) if h.Len() == 0 { delete(d, v-1) } } else { heap.Push(d[v], 1) } } for _, q := range d { if q.IntSlice[0] < 3 { return false } } return true } type hp struct{ sort.IntSlice } func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) } func (h *hp) Pop() any { a := h.IntSlice v := a[len(a)-1] h.IntSlice = a[:len(a)-1] return v }

All Problems

All Solutions