Skip to main content
Talentd
Talentd#1 Freshers Platform
Find Work
Learn
Tools
Post a JobFreeJoin Community
TalentdTalentd

Divide Array Into Increasing Sequences - Solution & Explanation

HardPremiumFree on FleetCodeArrayCounting7 min readAsked at: Google
Practice this problem

Problem Statement

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 1:

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.

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.

 

Constraints:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • nums is sorted in non-decreasing order.

Approach Overview

Problem Overview: You are given a non-decreasing array nums and an integer k. The task is to check whether you can divide the array into one or more subsequences such that every subsequence is strictly increasing and has length at least k.

Approach 1: Greedy Subsequence Construction (Simulation) (Time: O(n log n), Space: O(n))

A straightforward idea is to simulate building increasing subsequences. Since the array is already sorted, iterate through the elements and try to append each value to an existing subsequence that ends with a smaller value. A common implementation uses a min-heap or priority queue that tracks subsequence lengths and their last values. If the current value equals the last value of some subsequences, you must start new subsequences because duplicates cannot appear in a strictly increasing sequence. After processing all numbers, verify that every constructed subsequence has length at least k. This approach models the problem directly but introduces heap operations, making it O(n log n) time with O(n) extra space.

Approach 2: Counting Insight (Optimal) (Time: O(n), Space: O(1))

The sorted property unlocks a key observation. If a number appears f times, those f copies must belong to different subsequences because duplicates cannot be placed in the same strictly increasing sequence. Therefore, the minimum number of subsequences required is the maximum frequency of any value in the array. Let maxFreq be this value. Each subsequence must have length at least k, so the total number of elements must satisfy n ≥ maxFreq × k. If this condition holds, you can distribute elements across the maxFreq subsequences to maintain increasing order. Computing maxFreq requires a single pass over the array, making the solution O(n) time with constant space.

This reasoning relies on simple frequency counting and the non-decreasing order of the array. You only track runs of equal numbers and update the maximum frequency. No explicit subsequence construction is required.

Related concepts appear frequently in array problems and counting techniques, where identifying structural constraints removes the need for simulation.

Recommended for interviews: The counting insight is what interviewers expect. The greedy simulation demonstrates correct reasoning but wastes time maintaining data structures. Recognizing that duplicates force the minimum number of subsequences leads directly to the n ≥ maxFreq × k condition, giving a clean O(n) solution.

Approach 1: Quick Thinking

We assume that the array can be divided into m strictly increasing subsequences of length at least k. If the number of the most frequent number in the array is cnt, then these cnt numbers must be in different subsequences, so m geq cnt. Also, since the length of m subsequences is at least k, the fewer the number of subsequences, the better, so m = cnt. Therefore, cnt times k leq n must be satisfied. Hence, we only need to count the number of the most frequent number cnt in the array, and then judge whether cnt times k leq n. If it is, return true, otherwise return false.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array nums.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 2: Default Approach

Code

Java

Java

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Quick Thinking—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Subsequence Construction (Heap Simulation)O(n log n)O(n)When demonstrating the direct greedy idea of building subsequences step by step
Counting Insight (Max Frequency Rule)O(n)O(1)Best for interviews and production; uses the max frequency constraint to check feasibility instantly

Video Solution

LeetCode 1121 Divide Array Into Increasing Sequences • leetuition • 616 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Divide Array Into Increasing Sequences easy or hard?
LeetCode classifies it as Hard because the key insight is not obvious. Many candidates initially try to construct subsequences using greedy structures, but the intended solution reduces the problem to a simple counting constraint with O(n) complexity.
Divide Array Into Increasing Sequences Python/Java solution
In Python or Java, iterate through the sorted array, track consecutive equal values, and maintain the maximum frequency. After the pass, check whether nums.length ≥ maxFreq × k. If the condition holds return true, otherwise return false.
How to solve Divide Array Into Increasing Sequences in O(n)?
Iterate through the sorted array and track the length of each run of equal numbers to compute the maximum frequency. Let maxFreq be the largest count of a single value. Since duplicates cannot appear in the same increasing subsequence, you need at least maxFreq subsequences. The array can be divided only if n ≥ maxFreq × k.
What is the best approach for Divide Array Into Increasing Sequences?
The optimal approach uses a counting observation. Because the array is non-decreasing, duplicate values must belong to different subsequences. If the maximum frequency of any number is maxFreq, at least maxFreq subsequences are required. Each subsequence must have length ≥ k, so the condition n ≥ maxFreq × k determines whether the division is possible.
Is Divide Array Into Increasing Sequences asked at Google/Amazon/Meta?
This problem represents a common interview pattern around frequency counting and greedy reasoning on sorted arrays. Variants of the same idea appear in interviews at large tech companies where candidates must derive constraints from duplicates and sequence requirements.
What data structure is used in Divide Array Into Increasing Sequences?
The optimal solution relies mainly on counting frequencies while scanning the array, so it uses constant extra space. A more explicit greedy simulation may use a priority queue or heap to track subsequence lengths during construction.
What is the time complexity of Divide Array Into Increasing Sequences?
The optimal solution runs in O(n) time and O(1) space. You scan the array once to compute the maximum frequency of any value and check whether n ≥ maxFreq × k. A simulation-based greedy approach using heaps would take O(n log n) time.

Ready to solve this problem?

Practice Divide Array Into Increasing Sequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays