659 Split Array into Consecutive Subsequences

659. Split Array into Consecutive Subsequences

1. Question

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

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

Note:

1. The length of the input is in range of [1, 10000]

2. Implementation

(1) Heap

思路：建立一个map，每个序列当前结尾的number作为key, value是该number对应的minHeap,存储以该number结尾的序列的长度. 当一个number出现在两个或以上的序列的末端，我们尽量把number + 1加在最短的序列后面(所以用minHeap). 最后遍历整个map，当出现以key结尾的序列的长度小于3时，返回false

class Solution {
    public boolean isPossible(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        PriorityQueue<Integer> minHeap = null;
        for (int num : nums) {
            minHeap = map.getOrDefault(num - 1, new PriorityQueue<>());
            int len = minHeap.size() == 0 ? 0 : minHeap.remove();
            minHeap = map.getOrDefault(num, new PriorityQueue<>());
            minHeap.add(len + 1);
            map.put(num, minHeap);
        }

        for (int key : map.keySet()) {
            for (int len : map.get(key)) {
                if (len < 3) {
                    return false;
                }
            }
        }
        return true;
    }
}

(2) Two HashMap

(1) 用一个map记录每个number出现的次数，用另一个map记录当前的number是否可以加到一个现有的subsequence里

(2) 对于每个数，它要不成为一个有连续3个数的subsequence的开头，要不可以加在一个现有的subsequence里，如果这两个条件都不满足，说明该数组不能split成题目要求的subsequence

class Solution {
    public boolean isPossible(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return false;
        }

        Map<Integer, Integer> freq = new HashMap<>();
        Map<Integer, Integer> need = new HashMap<>();

        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        for (int num : nums) {
            if (freq.get(num) == 0) continue;

            // Current num can be appended to a subsequence
            if (need.getOrDefault(num, 0) > 0) {
                need.put(num, need.get(num) - 1);
                need.put(num + 1, need.getOrDefault(num + 1, 0) + 1);
            }
            // Current num be the start of a new subsequence
            else if (freq.getOrDefault(num + 1, 0) > 0 && freq.getOrDefault(num + 2, 0) > 0) {
                freq.put(num + 1, freq.get(num + 1) - 1);
                freq.put(num + 2, freq.get(num + 2) - 1);
                need.put(num + 3, need.getOrDefault(num + 3, 0) + 1);
            }
            // We can not split the array into subsequences with at least 3 consecutive numbers due to current number
            else {
                return false;
            }
            freq.put(num, freq.get(num) - 1);
        }
        return true;
    }
}

3. Time & Space Complexity

HashMap + Heap: 时间复杂度O(nlogk + nk),k为以num为结尾的subsequence的个数 空间复杂度O(nk)

Two HashMap: 时间复杂度O(n), 空间复杂度O(n)