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

Constraints:

• 1 <= nums.length <= 10000

---

Problem Analysis:

Suppose x is an item of array, if there exist x + 1 and x + 2 in the array, then it is a consecutive subsequence, or is not.

If consecutive number x + 3, x + 4, …, x + n exist, then the x, x + 1, …, x + n is a consecutive subsequence too.

So we iterate the ascend array, check item can merge into previous consecutive subsequence or it need to form a new subsequence.

---

Solution:

class Solution {
public:
  bool isPossible(vector<int>& nums) {
      unordered_map<int, int> count;
      unordered_map<int, int> tails;
      for (auto item: nums) ++count[item];      for (auto item: nums) {
          if (0 == count[item]) continue;
          --count[item];
          if (tails[item - 1] > 0) {
              --tails[item - 1];
              ++tails[item];
          } else if (count[item + 1] > 0 && count[item + 2] > 0) {
              --count[item + 1];
              --count[item + 2];
              ++tails[item + 2];
          } else {
              return false;
          }
      }
      
      return true;
  }
};

Time Complexity: O(n)

Space Complexity: O(n)