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

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

// 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(), []))

Java

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

// 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(), []))

659 - Split Array into Consecutive Subsequences

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions