LeetCode: Split Array into Consecutive Subsequences Posted on January 26, 2018July 26, 2020 by braindenny Split Array into Consecutive Subsequences Similar Problems: 132 Pattern Sum of Subarray Minimums LeetCode: Divide Array Into Increasing Sequences CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #subsequence, #inspiring, #splitarray, #greedy, #game 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 } Post Views: 9