How hard is LeetCode 1121. Divide Array Into Increasing Sequences?

LeetCode 1121. Divide Array Into Increasing Sequences is rated Hard on LeetCode.

What is the time complexity of LeetCode 1121. Divide Array Into Increasing Sequences?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1121. Divide Array Into Increasing Sequences?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1121. Divide Array Into Increasing Sequences cover?

LeetCode 1121. Divide Array Into Increasing Sequences is tagged Array and Counting on LeetCode.

Is LeetCode 1121. Divide Array Into Increasing Sequences a premium problem?

Yes. LeetCode 1121. Divide Array Into Increasing Sequences is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Divide Array Into Increasing Sequences — LeetCode 1121 Python Solution

HardLeetCode PremiumArrayCounting

Problem: #1121
Pattern: Hash Map
Reading time: 2 min
Source: leetcode.com

The problem

Given an integer array nums sorted in non-decreasing order and an integer k, return true if this array can be divided into one or more disjoint increasing subsequences of length at least k, or false otherwise.

Example

Input: nums = [1,2,2,3,3,4,4], k = 3
Output: true
Explanation: The array can be divided into two subsequences [1,2,3,4] and [2,3,4] with lengths at least 3 each.

Python solution

Python

class Solution:
    def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
        mx = max(len(list(x)) for _, x in groupby(nums))
        return mx * k <= len(nums)

Complexity

Measure	Complexity
Time	O(n)
Space	O(1) auxiliary

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1121. Divide Array Into Increasing Sequences is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1121. Divide Array Into Increasing Sequences?: LeetCode 1121. Divide Array Into Increasing Sequences is rated Hard on LeetCode.
What is the time complexity of LeetCode 1121. Divide Array Into Increasing Sequences?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1121. Divide Array Into Increasing Sequences?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1121. Divide Array Into Increasing Sequences cover?: LeetCode 1121. Divide Array Into Increasing Sequences is tagged Array and Counting on LeetCode.
Is LeetCode 1121. Divide Array Into Increasing Sequences a premium problem?: Yes. LeetCode 1121. Divide Array Into Increasing Sequences is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.