Minimum Number of Increasing Subsequence to Be Removed

Problem

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.

Examples

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^5
• 1 <= nums[i] <= 10^5

Solution

Method 1 – Greedy (Patience Sorting / Longest Decreasing Subsequence)

Intuition

Each operation removes a strictly increasing subsequence. The minimum number of such operations equals the length of the longest decreasing subsequence (LDS), by Dilworth's theorem.

Approach

1. Reverse nums to find the length of the longest increasing subsequence (LIS) in reversed array.
2. Use patience sorting (binary search) to compute LIS efficiently.
3. The answer is the length of the LIS in reversed array.

Code

C++

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int minOperations(vector<int>& nums) {
        vector<int> piles;
        for (int i = nums.size()-1; i >= 0; --i) {
            int x = nums[i];
            auto it = lower_bound(piles.begin(), piles.end(), x);
            if (it == piles.end()) piles.push_back(x);
            else *it = x;
        }
        return piles.size();
    }
};

Go

import "sort"
func minOperations(nums []int) int {
    piles := []int{}
    for i := len(nums)-1; i >= 0; i-- {
        x := nums[i]
        j := sort.SearchInts(piles, x)
        if j == len(piles) {
            piles = append(piles, x)
        } else {
            piles[j] = x
        }
    }
    return len(piles)
}

Java

import java.util.*;
class Solution {
    public int minOperations(int[] nums) {
        List<Integer> piles = new ArrayList<>();
        for (int i = nums.length-1; i >= 0; --i) {
            int x = nums[i];
            int j = Collections.binarySearch(piles, x);
            if (j < 0) j = -j-1;
            if (j == piles.size()) piles.add(x);
            else piles.set(j, x);
        }
        return piles.size();
    }
}

Kotlin

class Solution {
    fun minOperations(nums: IntArray): Int {
        val piles = mutableListOf<Int>()
        for (i in nums.indices.reversed()) {
            val x = nums[i]
            val j = piles.binarySearch(x).let { if (it < 0) -it-1 else it }
            if (j == piles.size) piles.add(x) else piles[j] = x
        }
        return piles.size
    }
}

Python

import bisect
class Solution:
    def minOperations(self, nums: list[int]) -> int:
        piles = []
        for x in reversed(nums):
            i = bisect.bisect_left(piles, x)
            if i == len(piles):
                piles.append(x)
            else:
                piles[i] = x
        return len(piles)

Rust

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut piles = Vec::new();
        for &x in nums.iter().rev() {
            match piles.binary_search(&x) {
                Ok(i) | Err(i) => {
                    if i == piles.len() { piles.push(x); }
                    else { piles[i] = x; }
                }
            }
        }
        piles.len() as i32
    }
}

TypeScript

class Solution {
    minOperations(nums: number[]): number {
        const piles: number[] = [];
        for (let i = nums.length-1; i >= 0; --i) {
            const x = nums[i];
            let l = 0, r = piles.length;
            while (l < r) {
                const m = (l + r) >> 1;
                if (piles[m] < x) l = m + 1; else r = m;
            }
            if (l === piles.length) piles.push(x);
            else piles[l] = x;
        }
        return piles.length;
    }
}

Complexity

• ⏰ Time complexity: O(n log n) — n = length of nums.
• 🧺 Space complexity: O(n) — for piles.