LeetCode: Divide Array Into Increasing Sequences Posted on August 31, 2019July 26, 2020 by braindenny Divide Array Into Increasing Sequences Similar Problems: LeetCode: Split Array into Consecutive Subsequences CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #game, #greedy, #splitarray Given a non-decreasing array of positive integers nums and an integer K, find out if this array can be divided into one or more disjoint increasing subsequences of length at least K. Example 1: Input: nums = [1,2,2,3,3,4,4], K = 3 Output: true Explanation: The array can be divided into the two subsequences [1,2,3,4] and [2,3,4] with lengths at least 3 each. Example 2: Input: nums = [5,6,6,7,8], K = 3 Output: false Explanation: There is no way to divide the array using the conditions required. Note: 1 <= nums.length <= 10^5 1 <= K <= nums.length 1 <= nums[i] <= 10^5 Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: greedy + get count of max frequency. O(n) time + O(1) space // https://code.dennyzhang.com/divide-array-into-increasing-sequences // Basic Ideas: Greedy // // Design algorithm // // Find the count of most frequent number, say m // We try to compose m subsequences. // If len(nums) >= m*K, we can always build up the subsequence // One way is avoiding putting the same number into one subsequence // Otherwise, it's impossible // // Complexity: Time O(n), Space O(1) // Basic Ideas: Greedy // // Design algorithm // // Find the count of most frequent number, say m // We try to compose m subsequences. // If len(nums) >= m*K, we can always build up the subsequence // One way is avoiding putting the same number into one subsequence // Otherwise, it's impossible // // Complexity: Time O(n), Space O(1) func canDivideIntoSubsequences(nums []int, K int) bool { maxFreq := 1 freq := 1 for i:=1; i<len(nums); i++ { if nums[i] > nums[i-1] { // a new group freq = 1 } else { // existing groups if nums[i] == nums[i-1] { freq++ } } if freq > maxFreq { maxFreq = freq } } return len(nums) >= maxFreq*K } Solution: greedy + get count of max frequency. O(n) time + O(n) space // https://code.dennyzhang.com/divide-array-into-increasing-sequences // Basic Ideas: Greedy // // Design algorithm // // Find the count of most frequent number, say m // We try to compose m subsequences. // If len(nums) >= m*K, we can always build up the subsequence // One way is avoiding putting the same number into one subsequence // Otherwise, it's impossible // // Complexity: Time O(n), Space O(n) func canDivideIntoSubsequences(nums []int, K int) bool { freqs := map[int]int{} maxFreq := 0 for _, v := range nums { freqs[v]++ if freqs[v] > maxFreq { maxFreq = freqs[v] } } return len(nums) >= maxFreq*K } Post Views: 0 Post navigation LeetCode: Design File SystemLeetCode: Longest Common Subsequence Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website