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 }