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

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

All Problems

All Solutions