Split Array into Consecutive Subsequences

Description

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

 

Solution(javascript)

// O(n)
// 先统计各个数字出现的次数，第一次出现的num，我们先把num+1, num+2加进 needed,
// 这时我们需要 num+3
const isPossible = (arr = []) => {
  const count = arr.reduce((acc, num) => {
    acc[num] = (acc[num] || 0) + 1
    return acc
  }, {})
  const needed = {}

  for (const num of arr) {
    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
}