Split Array into Consecutive Subsequences

Similar Problems:

- 132 Pattern
- Sum of Subarray Minimums
- Leetcode: Divide Array Into Increasing Sequences
- CheatSheet: Leetcode For Code Interview
- Tag: #subsequence, #inspiring, #splitarray, #greedy

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:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/split-array-into-consecutive-subsequences // Basic Ideas: greedy // When we loop the array from small to big, // it's always better append to existing subsequences, compared to start new ones. // Complexity: Time O(n), Space O(n) func isPossible(nums []int) bool { freqs := map[int]int{} appfreqs := map[int]int{} for _, n := range nums { freqs[n]++ } for _, n := range nums { // already used if freqs[n] == 0 { continue } // append to existing subsequences if appfreqs[n] > 0 { appfreqs[n]-- appfreqs[n+1]++ } else { // start a new one if freqs[n+1]>0 && freqs[n+2]>0 { freqs[n+1]-- freqs[n+2]-- appfreqs[n+3]++ } else { // dead return false } } freqs[n]-- } return true }