Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/659.html

 659. Split Array into Consecutive Subsequences

 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 1:

 Input: [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:

 Input: [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:

 Input: [1,2,3,4,4,5]
 Output: False

Algorithm

https://leetcode.com/problems/split-array-into-consecutive-subsequences/solution/

Code

• Java
• C++
• Python
• Go

•     class Solution {
          public boolean isPossible(int[] nums) {
              Integer prev = null;
              int prevCount = 0;
              Queue<Integer> starts = new LinkedList();
              int anchor = 0;
              for (int i = 0; i < nums.length; ++i) {
                  int t = nums[i];
                  if (i == nums.length - 1 || nums[i+1] != t) {
                      int count = i - anchor + 1;
                      if (prev != null && t - prev != 1) {
                          while (prevCount-- > 0)
                              if (prev < starts.poll() + 2) return false;
                          prev = null;
                      }
  
                      if (prev == null || t - prev == 1) {
                          while (prevCount > count) {
                              prevCount--;
                              if (t-1 < starts.poll() + 2)
                                  return false;
                          }
                          while (prevCount++ < count)
                              starts.add(t);
                      }
                      prev = t;
                      prevCount = count;
                      anchor = i+1;
                  }
              }
  
              while (prevCount-- > 0)
                  if (nums[nums.length - 1] < starts.poll() + 2)
                      return false;
              return true;
          }
      }
  
  
  ############
  
  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;
      }
  }
  

• // OJ: https://leetcode.com/problems/split-array-into-consecutive-subsequences/
  // Time: O(NlogN)
  // Space: O(N)
  class Solution {
  public:
      bool isPossible(vector<int>& nums) {
          map<int, int> m;
          for (int n : nums) m[n]++;
          while (m.size()) {
              auto i = m.begin();
              int cnt = 0, len = 0, prev = i->first - 1;
              while (i != m.end() && i->first == prev + 1 && i->second >= cnt) {
                  cnt = i->second;
                  prev = i->first;
                  if (!--i->second) i = m.erase(i);
                  else ++i;
                  ++len;
              }
              if (len < 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())
  
  ############
  
  class Solution(object):
    def isPossible(self, nums):
      """
      :type nums: List[int]
      :rtype: bool
      """
      d = collections.defaultdict(list)
      for num in nums:
        if d[num - 1]:
          heapq.heappush(d[num], heapq.heappop(d[num - 1]) + 1)
        else:
          heapq.heappush(d[num], 1)
      return not any(length < 3 for length in sum(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 interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
  func (h *hp) Pop() interface{} {
  	a := h.IntSlice
  	v := a[len(a)-1]
  	h.IntSlice = a[:len(a)-1]
  	return v
  }
  

• Java
• C++
• Python
• Go

• class Solution {
      public boolean isPossible(int[] nums) {
          Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
          Map<Integer, Integer> endMap = new HashMap<Integer, Integer>();
          for (int num : nums) {
              int count = countMap.getOrDefault(num, 0) + 1;
              countMap.put(num, count);
          }
          for (int num : nums) {
              int count = countMap.getOrDefault(num, 0);
              if (count > 0) {
                  int endCount = endMap.getOrDefault(num, 0);
                  if (endCount > 0) {
                      endMap.put(num, endCount - 1);
                      int nextCount = endMap.getOrDefault(num + 1, 0) + 1;
                      endMap.put(num + 1, nextCount);
                  } else {
                      int count1 = countMap.getOrDefault(num + 1, 0);
                      int count2 = countMap.getOrDefault(num + 2, 0);
                      if (count1 > 0 && count2 > 0) {
                          countMap.put(num + 1, count1 - 1);
                          countMap.put(num + 2, count2 - 1);
                          int endCount3 = endMap.getOrDefault(num + 3, 0) + 1;
                          endMap.put(num + 3, endCount3);
                      } else
                          return false;
                  }
                  countMap.put(num, count - 1);
              }
          }
          return true;
      }
  }
  
  ############
  
  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;
      }
  }
  

• // OJ: https://leetcode.com/problems/split-array-into-consecutive-subsequences/
  // Time: O(NlogN)
  // Space: O(N)
  class Solution {
  public:
      bool isPossible(vector<int>& nums) {
          map<int, int> m;
          for (int n : nums) m[n]++;
          while (m.size()) {
              auto i = m.begin();
              int cnt = 0, len = 0, prev = i->first - 1;
              while (i != m.end() && i->first == prev + 1 && i->second >= cnt) {
                  cnt = i->second;
                  prev = i->first;
                  if (!--i->second) i = m.erase(i);
                  else ++i;
                  ++len;
              }
              if (len < 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())
  
  ############
  
  class Solution(object):
    def isPossible(self, nums):
      """
      :type nums: List[int]
      :rtype: bool
      """
      d = collections.defaultdict(list)
      for num in nums:
        if d[num - 1]:
          heapq.heappush(d[num], heapq.heappop(d[num - 1]) + 1)
        else:
          heapq.heappush(d[num], 1)
      return not any(length < 3 for length in sum(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 interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
  func (h *hp) Pop() interface{} {
  	a := h.IntSlice
  	v := a[len(a)-1]
  	h.IntSlice = a[:len(a)-1]
  	return v
  }
  

All Problems

All Solutions