Maximum number of removal queries that can be processed i

Array Dynamic Programming

44.6% acceptance

Mar 31, 2026

You are given a 0-indexed array nums and a 0-indexed array queries. You can do the following operation at the beginning at most once: Replace nums with a subsequence of nums. We start processing queries in the given order; for each query, we do the following: If the first and the last element of nums is less than queries[i], the processing of queries ends. Otherwise, we choose either the first or the last element of nums if it is greater than or equal to queries[i], and we remove the chosen element from nums. Return the maximum number of queries that can be processed by doing the operation optimally.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_processable_queries(nums: Vec<i32>, queries: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut dp = vec![-1isize; n + 1];
    dp[0] = n as isize;
    let mut processed = 0;

    for query in queries {
      let mut next_from_left = vec![n; n + 1];
      for i in (0..n).rev() {
        next_from_left[i] = if nums[i] >= query {
          i
        } else {
          next_from_left[i + 1]
        };
      }

      let mut next_from_right = vec![-1isize; n + 1];
      for right in 1..=n {
        next_from_right[right] = if nums[right - 1] >= query {
          (right - 1) as isize
        } else {
          next_from_right[right - 1]
        };
      }

      let mut next_dp = vec![-1isize; n + 1];

      for left in 0..=n {
        let right = dp[left];
        if right < 0 {
          continue;
        }

        let right = right as usize;

        let left_pick = next_from_left[left];
        if left_pick < right {
          next_dp[left_pick + 1] = next_dp[left_pick + 1].max(right as isize);
        }

        let right_pick = next_from_right[right];
        if right_pick >= left as isize {
          next_dp[left] = next_dp[left].max(right_pick);
        }
      }

      if next_dp.iter().all(|&right| right < 0) {
        break;
      }

      dp = next_dp;
      processed += 1;
    }

    processed
  }
}