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.

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.

Description Hints 3 Solution Video 5:29

3231. Minimum Number of Increasing Subsequence to Be Removed

Q: 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.

Q: 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.

Hard47.9% acceptancePremium elsewhere, free here

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 <= 10⁵
1 <= nums[i] <= 10⁵

Topics

Array Binary Search

Hints open one at a time

Hint 1

Find the longest non-increasing subsequence.

Hint 2

No two elements of this sequence can be removed in one operation.

Hint 3

Try to prove that the answer is equal to the length of this sequence.

5:29

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[5,3,1,4,2]

Input

[1,2,3,4,5]

Input

[5,4,3,2,1]

Your code is saved on this device.Solution