Skip to content

3231. Minimum Number of Increasing Subsequence to Be Removed πŸ”’

Description

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

Solutions

We traverse the array $\textit{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 $\textit{nums}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        g = []
        for x in nums:
            l, r = 0, len(g)
            while l < r:
                mid = (l + r) >> 1
                if g[mid] < x:
                    r = mid
                else:
                    l = mid + 1
            if l == len(g):
                g.append(x)
            else:
                g[l] = x
        return len(g)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minOperations(int[] nums) {
        List<Integer> g = new ArrayList<>();
        for (int x : nums) {
            int l = 0, r = g.size();
            while (l < r) {
                int mid = (l + r) >> 1;
                if (g.get(mid) < x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l == g.size()) {
                g.add(x);
            } else {
                g.set(l, x);
            }
        }
        return g.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minOperations(vector<int>& nums) {
        vector<int> g;
        for (int x : nums) {
            int l = 0, r = g.size();
            while (l < r) {
                int mid = (l + r) >> 1;
                if (g[mid] < x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (l == g.size()) {
                g.push_back(x);
            } else {
                g[l] = x;
            }
        }
        return g.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func minOperations(nums []int) int {
    g := []int{}
    for _, x := range nums {
        l, r := 0, len(g)
        for l < r {
            mid := (l + r) >> 1
            if g[mid] < x {
                r = mid
            } else {
                l = mid + 1
            }
        }
        if l == len(g) {
            g = append(g, x)
        } else {