Maximum Number of Removal Queries That Can Be Processed I
HardUpdated: Aug 2, 2025
Practice on:
Problem
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
numswith a subsequence ofnums.
We start processing queries in the given order; for each query, we do the following:
- If the first and the last element of
numsis less thanqueries[i], the processing of queries ends. - Otherwise, we choose either the first or the last element of
numsif it is greater than or equal toqueries[i], and we remove the chosen element fromnums.
Return themaximum number of queries that can be processed by doing the operation optimally.
Examples
Example 1:
Input: nums = [1,2,3,4,5], queries = [1,2,3,4,6]
Output: 4
Explanation: We don't do any operation and process the queries as follows:
1- We choose and remove nums[0] since 1 <= 1, then nums becomes [2,3,4,5].
2- We choose and remove nums[0] since 2 <= 2, then nums becomes [3,4,5].
3- We choose and remove nums[0] since 3 <= 3, then nums becomes [4,5].
4- We choose and remove nums[0] since 4 <= 4, then nums becomes [5].
5- We can not choose any elements from nums since they are not greater than or equal to 5.
Hence, the answer is 4.
It can be shown that we can't process more than 4 queries.
Example 2:
Input: nums = [2,3,2], queries = [2,2,3]
Output: 3
Explanation: We don't do any operation and process the queries as follows:
1- We choose and remove nums[0] since 2 <= 2, then nums becomes [3,2].
2- We choose and remove nums[1] since 2 <= 2, then nums becomes [3].
3- We choose and remove nums[0] since 3 <= 3, then nums becomes [].
Hence, the answer is 3.
It can be shown that we can't process more than 3 queries.
Example 3:
Input: nums = [3,4,3], queries = [4,3,2]
Output: 2
Explanation: First we replace nums with the subsequence of nums [4,3].
Then we can process the queries as follows:
1- We choose and remove nums[0] since 4 <= 4, then nums becomes [3].
2- We choose and remove nums[0] since 3 <= 3, then nums becomes [].
3- We can not process any more queries since nums is empty.
Hence, the answer is 2.
It can be shown that we can't process more than 2 queries.
Constraints:
1 <= nums.length <= 10001 <= queries.length <= 10001 <= nums[i], queries[i] <= 10^9
Solution
Method 1 – Dynamic Programming with Two Pointers
Intuition
We can remove a prefix and/or suffix of the array at most once (by picking a subsequence), and then process queries greedily from both ends. The optimal solution is to try all possible subarrays (as subsequences) and simulate the process for each, keeping the maximum number of queries processed.
Approach
- For every possible subarray
[l, r]ofnums(wherel <= r), treat it as the chosen subsequence. - For each subarray, simulate the query process:
- For each query, if both ends are less than the query, stop.
- Otherwise, remove the left or right end if it is greater than or equal to the query.
- Continue until no more queries can be processed or the subarray is empty.
- Track the maximum number of queries processed over all possible subarrays.
- Return the maximum found.
Code
C++
class Solution {
public:
int maxQueries(vector<int>& nums, vector<int>& queries) {
int n = nums.size(), m = queries.size(), ans = 0;
for (int l = 0; l < n; ++l) {
for (int r = l; r < n; ++r) {
int i = l, j = r, q = 0;
while (i <= j && q < m) {
if (nums[i] < queries[q] && nums[j] < queries[q]) break;
if (nums[i] >= queries[q]) i++;
else j--;
q++;
}
ans = max(ans, q);
}
}
return ans;
}
};
Go
func maxQueries(nums []int, queries []int) int {
n, m, ans := len(nums), len(queries), 0
for l := 0; l < n; l++ {
for r := l; r < n; r++ {
i, j, q := l, r, 0
for i <= j && q < m {
if nums[i] < queries[q] && nums[j] < queries[q] {
break
}
if nums[i] >= queries[q] {
i++
} else {
j--
}
q++
}
if q > ans {
ans = q
}
}
}
return ans
}
Java
class Solution {
public int maxQueries(int[] nums, int[] queries) {
int n = nums.length, m = queries.length, ans = 0;
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
int i = l, j = r, q = 0;
while (i <= j && q < m) {
if (nums[i] < queries[q] && nums[j] < queries[q]) break;
if (nums[i] >= queries[q]) i++;
else j--;
q++;
}
ans = Math.max(ans, q);
}
}
return ans;
}
}
Kotlin
class Solution {
fun maxQueries(nums: IntArray, queries: IntArray): Int {
val n = nums.size
val m = queries.size
var ans = 0
for (l in 0 until n) {
for (r in l until n) {
var i = l
var j = r
var q = 0
while (i <= j && q < m) {
if (nums[i] < queries[q] && nums[j] < queries[q]) break
if (nums[i] >= queries[q]) i++
else j--
q++
}
ans = maxOf(ans, q)
}
}
return ans
}
}
Python
class Solution:
def maxQueries(self, nums: list[int], queries: list[int]) -> int:
n, m, ans = len(nums), len(queries), 0
for l in range(n):
for r in range(l, n):
i, j, q = l, r, 0
while i <= j and q < m:
if nums[i] < queries[q] and nums[j] < queries[q]:
break
if nums[i] >= queries[q]:
i += 1
else:
j -= 1
q += 1
ans = max(ans, q)
return ans
Rust
impl Solution {
pub fn max_queries(nums: Vec<i32>, queries: Vec<i32>) -> i32 {
let n = nums.len();
let m = queries.len();
let mut ans = 0;
for l in 0..n {
for r in l..n {
let (mut i, mut j, mut q) = (l, r, 0);
while i <= j && q < m {
if nums[i] < queries[q] && nums[j] < queries[q] { break; }
if nums[i] >= queries[q] { i += 1; }
else { j -= 1; }
q += 1;
}
ans = ans.max(q);
}
}
ans as i32
}
}
TypeScript
class Solution {
maxQueries(nums: number[], queries: number[]): number {
const n = nums.length, m = queries.length;
let ans = 0;
for (let l = 0; l < n; l++) {
for (let r = l; r < n; r++) {
let i = l, j = r, q = 0;
while (i <= j && q < m) {
if (nums[i] < queries[q] && nums[j] < queries[q]) break;
if (nums[i] >= queries[q]) i++;
else j--;
q++;
}
ans = Math.max(ans, q);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2 * m)— We try all subarrays (O(n^2)) and for each, simulate up tomqueries. - 🧺 Space complexity:
O(1)— Only a constant amount of extra space is used for pointers and counters.