Skip to main content
Talentd

Minimum Number of Increasing Subsequence to Be Removed - Solution & Explanation

HardPremiumFree on FleetCodeArrayBinary Search9 min read
Practice this problem

Problem Statement

Given an array of integers nums, you are allowed to perform the following operation any number of times:

  • Remove a strictly increasing subsequence from the array.

Your task is to find the minimum number of operations required to make the array empty.

 

Example 1:

Input: nums = [5,3,1,4,2]

Output: 3

Explanation:

We remove subsequences [1, 2], [3, 4], [5].

Example 2:

Input: nums = [1,2,3,4,5]

Output: 1

Example 3:

Input: nums = [5,4,3,2,1]

Output: 5

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approach Overview

Problem Overview: You are given an array and repeatedly remove strictly increasing subsequences. The goal is to minimize how many such subsequences are needed to remove the entire array.

The key observation comes from sequence partitioning theory: the minimum number of strictly increasing subsequences required to cover the array equals the length of the longest non‑increasing subsequence. Instead of explicitly constructing subsequences, you can compute this value efficiently.

Approach 1: Dynamic Programming (O(n2) time, O(n) space)

A straightforward method computes the longest non‑increasing subsequence using classic DP. For each index i, iterate through all previous indices j < i. If nums[j] >= nums[i], extend the subsequence ending at j to i. Track the maximum length across all positions. The final length represents the minimum number of increasing subsequences needed to remove the array. This approach is easy to reason about but becomes slow for large inputs because every pair of indices is compared.

Approach 2: Greedy + Binary Search (O(n log n) time, O(n) space)

The optimal approach adapts the patience sorting technique used for LIS problems. Maintain an array tails where each value represents the smallest possible ending value of a non‑increasing subsequence of a given length. Iterate through the array and use binary search to find the position where the current element should update tails. If the element extends the sequence, append it; otherwise replace the appropriate position. This greedy replacement keeps subsequence endings as flexible as possible and guarantees the longest non‑increasing subsequence length is found.

Binary search ensures each insertion or replacement runs in O(log n), giving overall O(n log n) time. The size of tails at the end equals the answer: the minimum number of increasing subsequences required to remove the array.

This pattern appears frequently in problems involving subsequence partitioning and ordering constraints. If you want to strengthen the underlying concepts, review array traversal patterns and binary search optimizations used in LIS-style problems under binary search.

Recommended for interviews: Interviewers expect the Greedy + Binary Search solution. Starting with the quadratic DP demonstrates understanding of subsequences, but optimizing it to O(n log n) using patience sorting shows strong algorithmic maturity and familiarity with sequence optimization techniques.

Solution

We traverse the array nums from left to right. For each element x, we need to greedily append it after the last element of the preceding sequence that is smaller than x. If no such element is found, it means the current element x is smaller than all elements in the preceding sequences, and we need to start a new sequence with x.

From this analysis, we can observe that the last elements of the preceding sequences are in a monotonically decreasing order. Therefore, we can use binary search to find the position of the first element in the preceding sequences that is smaller than x, and then place x in that position.

Finally, we return the number of sequences.

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

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming (Longest Non‑Increasing Subsequence)O(n^2)O(n)Useful for understanding the subsequence relationship or when input size is small
Greedy + Binary Search (Patience Sorting)O(n log n)O(n)Optimal approach for large arrays and typical interview expectations

Video Solution

5 Simple Steps for Solving Dynamic Programming Problems • Reducible • 1,234,244 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Increasing Subsequence to Be Removed easy or hard?
The problem is classified as Hard because it requires recognizing the connection to the longest non‑increasing subsequence and applying a patience sorting style optimization. Without that insight, many solutions fall back to slower O(n^2) dynamic programming.
Minimum Number of Increasing Subsequence to Be Removed Python/Java solution
Most implementations follow the same Greedy + Binary Search template. Maintain a list of subsequence endings, use binary search to find the correct index, and update the list accordingly. This pattern works consistently across Python, Java, C++, Go, TypeScript, and Rust with O(n log n) time complexity.
How to solve Minimum Number of Increasing Subsequence to Be Removed in O(n log n)?
Maintain a tails array that tracks the smallest possible ending value for non‑increasing subsequences of each length. For every number in the array, use binary search to find where it should replace or extend a value in tails. This greedy update keeps subsequences flexible and builds the longest non‑increasing subsequence length in O(n log n) time.
What is the best approach for Minimum Number of Increasing Subsequence to Be Removed?
The optimal approach uses Greedy combined with Binary Search, similar to the patience sorting technique used in LIS problems. Instead of explicitly forming subsequences, compute the length of the longest non‑increasing subsequence. That length equals the minimum number of strictly increasing subsequences needed to remove the array. The algorithm runs in O(n log n) time with O(n) space.
Is Minimum Number of Increasing Subsequence to Be Removed asked at Google/Amazon/Meta?
Subsequence partitioning and LIS‑style optimization problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving greedy strategies and binary search are especially common in algorithm rounds.
What data structure is used in Minimum Number of Increasing Subsequence to Be Removed?
The core structure is a dynamic array (often called tails) combined with binary search. The array stores candidate subsequence endings while binary search determines where the current element should update the structure efficiently.
What is the time complexity of Minimum Number of Increasing Subsequence to Be Removed?
The optimal solution runs in O(n log n) time using a Greedy + Binary Search strategy. Each element is processed once, and a binary search is used to update the correct subsequence position. A simpler dynamic programming approach exists with O(n^2) time and O(n) space.

Ready to solve this problem?

Practice Minimum Number of Increasing Subsequence to Be Removed with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays