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:
nums with a subsequence of nums.We start processing queries in the given order; for each query, we do the following:
nums is less than queries[i], the processing of queries ends.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 <= 10001 <= queries.length <= 10001 <= nums[i], queries[i] <= 109Problem 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.
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]:
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]]).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]]).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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS with Memoization | O(q^2) | O(q^2) | Useful for understanding the decision tree and validating transitions during problem exploration |
| Dynamic Programming on Removal Counts | O(q^2) | O(q) | Preferred production and interview solution; tracks left removals and derives right index efficiently |
【每日一题】LeetCode 3018. Maximum Number of Removal Queries That Can Be Processed I • Huifeng Guan • 283 views views
Watch 1 more video solutions →Practice Maximum Number of Removal Queries That Can Be Processed I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor