Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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. 1 <= nums.length <= 10^5
  2. 1 <= K <= nums.length
  3. 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
}
linkedin
github
slack

Post Views: 0
Posted in MediumTagged #game, #greedy, #inspiring, splitarray

Post navigation

LeetCode: Design File System
LeetCode: Longest Common Subsequence

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.