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

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