Brian Yang
Brian Yang
algorithm designer
Feb 28, 2020 2 min read

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

 

Solution

var isPossible = function (nums) {
  let count = {}, tail = {}

  for (let n of nums) {
    count[n] = count[n] ? count[n] + 1 : 1
  }

  for (let n of nums) {
    if (count[n] === 0) {
      continue
    } else if (tail[n] > 0) {
      tail[n] -= 1
      tail[n + 1] = tail[n + 1] ? tail[n + 1] + 1 : 1
    } else if (count[n + 1] > 0 && count[n + 2] > 0) {
      count[n + 1] -= 1
      count[n + 2] -= 1
      tail[n + 3] = tail[n + 3] ? tail[n + 3] + 1 : 1
    } else {
      return false
    }
    count[n] -= 1
  }
  return true
};
« All Possible Full Binary Trees Caesar Cipher »
comments powered by Disqus