# 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}$.

• 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()) {
} else {
g.set(l, x);
}
}
return g.size();
}
}

• 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();
}
};

• 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)


• 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 {
g[l] = x
}
}
return len(g)
}

• function minOperations(nums: number[]): number {
const g: number[] = [];
for (const x of nums) {
let [l, r] = [0, g.length];
while (l < r) {
const mid = (l + r) >> 1;
if (g[mid] < x) {
r = mid;
} else {
l = mid + 1;
}
}
if (l === g.length) {
g.push(x);
} else {
g[l] = x;
}
}
return g.length;
}


• impl Solution {
pub fn min_operations(nums: Vec<i32>) -> i32 {
let mut g = Vec::new();
for &x in nums.iter() {
let mut l = 0;
let mut r = g.len();
while l < r {
let mid = (l + r) / 2;
if g[mid] < x {
r = mid;
} else {
l = mid + 1;
}
}
if l == g.len() {
g.push(x);
} else {
g[l] = x;
}
}
g.len() as i32
}
}