659. Split Array into Consecutive Subsequences

Problem

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

• Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).

• All subsequences have a length of 3** or more**.

Return true** if you can split nums according to the above conditions, or false otherwise**.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

  Example 1:

Input: nums = [1,2,3,3,4,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]
Output: true
Explanation: nums can be split into the following subsequences:
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

Example 3:

Input: nums = [1,2,3,4,4,5]
Output: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

  Constraints:

• 1 <= nums.length <= 10^4

• -1000 <= nums[i] <= 1000

• nums is sorted in non-decreasing order.

Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isPossible = function(nums) {
  const count = nums.reduce((acc, num) => {
    acc[num] = (acc[num] || 0) + 1
    return acc
  }, {})
  const needed = {}

  for (const num of nums) {
    if (count[num] <= 0) {
      continue // eslint-disable-line
    }
    count[num] -= 1
    if (needed[num] > 0) {
      needed[num] -= 1
      needed[num + 1] = (needed[num + 1] || 0) + 1
    } else if (count[num + 1] > 0 && count[num + 2]) {
      count[num + 1] -= 1
      count[num + 2] -= 1
      needed[num + 3] = (needed[num + 3] || 0) + 1
    } else {
      return false
    }
  }
  return true
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).