Skip to main content
Talentd

Maximum Number of Removal Queries That Can Be Processed I - Solution & Explanation

HardPremiumFree on FleetCodeArrayDynamic Programming13 min read
Practice this problem

Problem Statement

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.

 

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 <= 1000
  • 1 <= queries.length <= 1000
  • 1 <= nums[i], queries[i] <= 109

Approach Overview

Problem Overview: You have an array nums and a sequence of removal queries. For each query value, you may remove either the leftmost or rightmost element of the array if the element is less than or equal to the query value. Queries must be processed in order. The goal is to determine the maximum number of queries that can be successfully processed.

Approach 1: Recursive Search with Memoization (O(q^2) time, O(q^2) space)

At query index i, the remaining array is defined by how many elements have already been removed from the left and right. Try both valid options: remove the left element if nums[l] ≤ queries[i], or remove the right element if nums[r] ≤ queries[i]. A recursive DFS explores both possibilities and returns the maximum number of processed queries. Since many states repeat, cache results using memoization keyed by (i, l), where l is how many elements were removed from the left and the right index can be derived. This avoids recomputing overlapping subproblems and turns exponential branching into a quadratic state space. The approach highlights the decision structure clearly but still uses extra memory.

Approach 2: Dynamic Programming on Removed Counts (O(q^2) time, O(q) space)

Instead of tracking explicit subarrays, represent the state by how many queries have been processed and how many elements were removed from the left. Suppose i queries have been processed and l removals came from the left. Then the right side removals are i - l, and the current right index becomes n - 1 - (i - l). Check if the next query allows removing from the left (nums[l] ≤ queries[i]) or from the right (nums[r] ≤ queries[i]). Update the next DP state accordingly. Iterating through queries builds reachable states and tracks the largest i for which a valid configuration exists. This formulation converts the branching process into a structured DP over counts, making it efficient and straightforward to implement.

The problem mainly tests modeling state transitions over shrinking boundaries of an array. The DP state captures how many elements were removed from each side rather than storing the remaining array explicitly. Similar patterns appear in problems involving decisions on both ends of an array, often solved with Dynamic Programming over intervals or counts. Efficient indexing and careful state transitions are key when working with Array boundaries and sequential constraints.

Recommended for interviews: The dynamic programming approach is what interviewers expect. Brute-force recursion shows the correct intuition about choosing left or right per query, but the DP formulation demonstrates the ability to compress the state and avoid exponential exploration. Showing how the right index is derived from the number of processed queries is usually the key insight that unlocks the optimal solution.

Solution

We define f[i][j] as the maximum number of queries we can handle when the numbers in the interval [i, j] have not been deleted yet.

Consider f[i][j]:

  • If i > 0, the value of f[i][j] can be transferred from f[i - 1][j]. If nums[i - 1] \ge queries[f[i - 1][j]], we can choose to delete nums[i - 1]. Therefore, we have f[i][j] = f[i - 1][j] + (nums[i - 1] \ge queries[f[i - 1][j]]).
  • If j + 1 < n, the value of f[i][j] can be transferred from f[i][j + 1]. If nums[j + 1] \ge queries[f[i][j + 1]], we can choose to delete nums[j + 1]. Therefore, we have f[i][j] = f[i][j + 1] + (nums[j + 1] \ge queries[f[i][j + 1]]).
  • If f[i][j] = m, we can directly return m.

The final answer is max\limits_{0 \le i < n} f[i][i] + (nums[i] \ge queries[f[i][i]]).

The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFS with MemoizationO(q^2)O(q^2)Useful for understanding the decision tree and validating transitions during problem exploration
Dynamic Programming on Removal CountsO(q^2)O(q)Preferred production and interview solution; tracks left removals and derives right index efficiently

Video Solution

【每日一题】LeetCode 3018. Maximum Number of Removal Queries That Can Be Processed I • Huifeng Guan • 284 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximum Number of Removal Queries That Can Be Processed I easy or hard?
The problem is rated Hard because it requires modeling the shrinking array using counts rather than explicitly modifying the array. Recognizing that the right boundary can be derived from the number of processed queries is the key insight that leads to the O(q^2) dynamic programming solution.
Maximum Number of Removal Queries That Can Be Processed I Python/Java solution
Implement the DP where dp[l] indicates if l left removals are possible after processing i queries. For each query, compute the current left index l and right index n - 1 - (i - l) and update states if the corresponding values satisfy the query limit. The same logic translates directly across Python, Java, C++, Go, and TypeScript.
How to solve Maximum Number of Removal Queries That Can Be Processed I in O(q^2)?
Define a DP state where dp[l] represents whether it is possible to process i queries with l removals from the left. The right removals become i - l, so the current right index is n - 1 - (i - l). For each query, check whether the left or right element satisfies the query constraint and update the next state accordingly.
What is the best approach for Maximum Number of Removal Queries That Can Be Processed I?
Dynamic Programming based on how many elements are removed from the left side works best. If i queries have been processed and l elements were removed from the left, the right index can be derived from the remaining count. This reduces the state space to O(q^2) and avoids exponential branching from trying both ends at every step.
Is Maximum Number of Removal Queries That Can Be Processed I asked at Google/Amazon/Meta?
Problems combining array boundary decisions with dynamic programming frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variants that involve choosing elements from either end with constraints are especially common in dynamic programming interview rounds.
What data structure is used in Maximum Number of Removal Queries That Can Be Processed I?
The core data structure is a dynamic programming array that tracks how many elements were removed from the left side after processing a certain number of queries. The array indices implicitly represent the shrinking boundaries of the original array.
What is the time complexity of Maximum Number of Removal Queries That Can Be Processed I?
The optimal dynamic programming solution runs in O(q^2) time where q is the number of queries. For each processed query, the algorithm iterates over possible counts of elements removed from the left side. Space complexity can be optimized to O(q) using rolling DP.

Ready to solve this problem?

Practice Maximum Number of Removal Queries That Can Be Processed I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays