Question

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

Solution 1

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())

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;
  }
};

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
}