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:

1
2
3
4

Input: nums = [5,3,1,4,2]
Output: 3
Explanation:
We remove subsequences `[1, 2]`, `[3, 4]`, `[5]`.

Example 2:

1
2

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

Example 3:

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#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();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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.