Welcome to Subscribe On Youtube

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

Solution 1: Greedy + Binary Search

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

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

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

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

All Problems

All Solutions