3018. Maximum Number of Removal Queries That Can Be Processed I
Problem Description
You are provided with two arrays: nums which is the main array with 0-indexed elements, and queries, also a 0-indexed array containing query elements. Your task is to process the elements in queries sequentially by following a set of rules:
-
You can initially choose to replace
numswith any of its subsequences. This operation is optional and can be performed only once. -
Each element in
queriesis processed according to this procedure:- Check the first and last element of
nums. If both are smaller than the current query element, stop processing further queries. - If not, you must choose and remove an element from either end of
nums, provided that the chosen element is greater than or equal to the query element.
- Check the first and last element of
Your goal is to determine the maximum number of queries that can be processed if you choose to perform the initial operation optimally.
Intuition
To arrive at the solution, we need to keep track of the range within nums we have available for answering queries. A dynamic programming (DP) approach is suitable for this situation. Wherein we define a DP table f where each entry f[i][j] represents the maximum number of queries we can process when the subarray of nums from i to j (inclusive) is still intact.
The solution must account for two possible actions for each element of queries:
- If we choose to delete the first element of our current subarray, we must have a way to store and use the result of this action for further decisions.
- Likewise, if we choose to delete the last element, that decision's impact should also be recorded and available for upcoming queries.
The answer can be built iteratively. For each entry f[i][j], we consider the implications of removing an element from the beginning (i-1) or the end (j+1) of the subarray. The choice depends on whether the elements on the edges satisfy the condition with regard to the current query element.
By updating the DP table this way, when f[i][j] equals the total number of queries, we can immediately return this number, as we can't process more queries than we have. If this case isn't reached, the final answer is the maximum value of f[i][i] plus the condition that nums[i] must be greater than or equal to queries[f[i][i]]. This condition checks if we can take one more query when the subarray is reduced to a single element.
The intuition is that, with careful selection of which element to delete when processing each query and using DP to memorize our choices' outcomes, we can determine the optimal way to process the maximum number of queries.
Learn more about Dynamic Programming patterns.
How many ways can you arrange the three letters A, B and C?
Solution Approach
The given solution uses Dynamic Programming (DP), a common technique for solving problems where subproblems overlap, and solutions can be built upon previously solved subproblems to reach the overall solution.
The key data structure used is a two-dimensional array f of size n x n, where n is the length of nums. Each entry f[i][j] in this DP table holds the maximum number of queries the algorithm can process given that we are considering nums[i] through nums[j] as the current range.
Here's how the implementation of dynamic programming works step by step:
-
Iterate over all possible subarrays of
numsby using two nested loops. The outer loop variableirefers to the beginning of the subarray, and the inner loop variablej(which starts fromn - 1and moves backwards toi) refers to the end of the subarray. -
At each iteration
(i, j), we try to updatef[i][j]using two possible actions:-
If we remove the first element of the subarray (
nums[i - 1]wheni > 0), we consider the value inf[i - 1][j], as this represents the maximum number of queries processed whennums[i - 1]is included. Ifnums[i - 1]is greater than or equal to the current query (indicated byqueries[f[i - 1][j]]), we can increment the number of processed queries by 1. -
Similarly, if we decide to remove the last element of the subarray (
nums[j + 1]whenj + 1 < n), we consider the value inf[i][j + 1]. Again, ifnums[j + 1]satisfies the current query, the value off[i][j]can be incremented.
-
-
During the iteration, if at any point
f[i][j]equalsm, the total number of queries, we know that we can process all the queries. Thus, we returnmimmediately, as it's the maximum possible. -
If the loop completes without returning, it means not all queries can be processed. The final step is to find the maximum of
f[i][i]for allifrom0ton - 1. We add 1 tof[i][i]ifnums[i]is greater than or equal to the 'next' query (queries[f[i][i]]) to consider the possibility of processing one more query.
The choice of using a 2D DP table is necessitated by the need to maintain a count of processed queries across different subarray configurations. It allows us to make decisions based on the range of elements available at each step and optimize the number of queries processed.
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?
Example Walkthrough
Let's say we have the following nums and queries arrays:
- nums = [3, 5, 1, 4]
- queries = [2, 4, 6]
With nums being [3, 5, 1, 4], we have the option to replace nums with any of its subsequences. Since we have a 0-based index, the initial nums array is from index 0 to index 3.
We'll initialize our DP table f with the dimensions of the nums array. In this case, we have 4 elements, so our table f will be a 4x4 2D array.
Now, we'll iterate over the queries and nums to fill in the DP table:
-
The first query is 2. We start with subarray
i=0,j=3, which is [3, 5, 1, 4].- At
f[0][3], none of the edge elements (3 and 4) are smaller than the query (2), so we can remove a value. We choose to remove 3 from the beginning, which makes our subarray now [5, 1, 4], and setf[1][3]to 1, as we have processed one query.
- At
-
We continue with subarray
i=1,j=3, and the same query.- At
f[1][3], again the edge elements (5 and 4) are not smaller than 2, so we can remove another value. We can choose either 5 or 4. We remove 5 and setf[2][3]to 2, as we have processed another query.
- At
-
Now the subarray
i=2,j=3is [1, 4], and we move on to the next query, which is 4.- At
f[2][3], the edge elements (1 and 4) are not both smaller than the query (4), so we can only remove the last element 4. Now our subarray is [1], andf[3][3]is set to 3.
- At
-
As our subarray
i=3,j=3is just [1] and we have the final query 6, we cannot process this query because the remaining element is smaller than 6.
Now we have completed the iterations. We look at our DP table f and find the maximum value of f[i][i]:
f[0][0]would consider only [3], but since there's no query <= 3 after processing 2, it stays 0.f[1][1]would consider only [5], which is >= 2 and 4, so we could have processed 2 queries if it was a singleton from the start.f[2][2]would consider only [1], which is < 2, so it stays 0.f[3][3]ends up as 3 because we remove 4 in response to query 4.
The max value we find is f[3][3], so the answer is 3. We processed 3 queries successfully before we were left with an element smaller than the next query.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maximumProcessableQueries(self, processes: List[int], queries: List[int]) -> int:
5 # Number of processes
6 num_processes = len(processes)
7 # Initialize a 2D array for the dynamic programming table with zeros
8 dp_table = [[0] * num_processes for _ in range(num_processes)]
9 # Number of queries
10 num_queries = len(queries)
11
12 # Fill in the dp_table for all possible segments [i, j] of processes
13 for i in range(num_processes):
14 for j in range(num_processes - 1, i - 1, -1):
15 # If we're not in the first row, check whether we can include the process at i-1
16 if i:
17 dp_table[i][j] = max(
18 dp_table[i][j], # Current value
19 # If the current process can handle the next query,
20 # add 1 to the value from the row above
21 dp_table[i - 1][j] + (processes[i - 1] >= queries[dp_table[i - 1][j]])
22 )
23 # If we're not in the last column, check whether we can include the process at j+1
24 if j + 1 < num_processes:
25 dp_table[i][j] = max(
26 dp_table[i][j], # Current value
27 # If the current process can handle the next query,
28 # add 1 to the value from the next column
29 dp_table[i][j + 1] + (processes[j + 1] >= queries[dp_table[i][j + 1]])
30 )
31 # If we have found a solution for all queries, return the total number of queries
32 if dp_table[i][j] == num_queries:
33 return num_queries
34
35 # Iterate over the main diagonal of the dp_table to return the maximum value
36 # This indicates how many queries can be processed starting and ending at each process
37 return max(dp_table[i][i] + (processes[i] >= queries[dp_table[i][i]]) for i in range(num_processes))
381class Solution {
2 public int maximumProcessableQueries(int[] nums, int[] queries) {
3 int n = nums.length; // Total number of nums.
4 // Create a 2D array to store the results of subproblems.
5 int[][] dp = new int[n][n];
6 int m = queries.length; // Total number of queries.
7
8 // Build the dp array in bottom-up fashion.
9 for (int i = 0; i < n; ++i) {
10 for (int j = n - 1; j >= i; --j) {
11 // Check and update using the previous row's data if not in the first row.
12 if (i > 0) {
13 dp[i][j] = Math.max(
14 dp[i][j], // Current value.
15 dp[i - 1][j] + (nums[i - 1] >= queries[dp[i - 1][j]] ? 1 : 0)); // Compare with previous row.
16 }
17 // Check and update using the data from the next column if not in the last column.
18 if (j + 1 < n) {
19 dp[i][j] = Math.max(
20 dp[i][j], // Current value.
21 dp[i][j + 1] + (nums[j + 1] >= queries[dp[i][j + 1]] ? 1 : 0)); // Compare with next column.
22 }
23 // If we have found all queries to be processable, return the total count.
24 if (dp[i][j] == m) {
25 return m;
26 }
27 }
28 }
29
30 // Variable to hold the maximum number of processable queries observed.
31 int maxQueries = 0;
32 // Iterate through the diagonal elements of dp array to find the maximum.
33 for (int i = 0; i < n; ++i) {
34 maxQueries = Math.max(maxQueries, dp[i][i] + (nums[i] >= queries[dp[i][i]] ? 1 : 0));
35 }
36
37 // Return the maximum number of processable queries.
38 return maxQueries;
39 }
40}
411class Solution {
2public:
3 int maximumProcessableQueries(vector<int>& nums, vector<int>& queries) {
4 int numElements = nums.size(); // Number of elements in nums
5 int dp[numElements][numElements]; // Dynamic programming table
6 memset(dp, 0, sizeof(dp)); // Initialize all DP values to 0
7 int numQueries = queries.size(); // Number of queries
8
9 // Outer loop to handle the start of the subarray
10 for (int start = 0; start < numElements; ++start) {
11 // Inner loop to handle the end of the subarray, going backwards
12 for (int end = numElements - 1; end >= start; --end) {
13 if (start > 0) {
14 // If nums[start - 1] can process the current query, we increment the count from the previous state
15 dp[start][end] = max(dp[start][end], dp[start - 1][end] + (nums[start - 1] >= queries[dp[start - 1][end]] ? 1 : 0));
16 }
17 if (end + 1 < numElements) {
18 // If nums[end + 1] can process the current query, we increment the count from the previous state
19 dp[start][end] = max(dp[start][end], dp[start][end + 1] + (nums[end + 1] >= queries[dp[start][end + 1]] ? 1 : 0));
20 }
21 // If we have processed all queries, we can return the total number of queries as answer
22 if (dp[start][end] == numQueries) {
23 return numQueries;
24 }
25 }
26 }
27
28 int answer = 0; // Variable to store the maximum number of queries processed
29
30 // Iterate over all elements to find the maximum number of queries that can be processed
31 for (int i = 0; i < numElements; ++i) {
32 // Check if the current element can process the next query and
33 // update the answer with the maximum value obtained from the DP table
34 answer = max(answer, dp[i][i] + (nums[i] >= queries[dp[i][i]] ? 1 : 0));
35 }
36
37 return answer; // Return the final answer
38 }
39};
401function maximumProcessableQueries(nums: number[], queries: number[]): number {
2 const numLength = nums.length;
3 // Initialize the memoization array with zeros
4 const dp: number[][] = Array.from({ length: numLength }, () => new Array(numLength).fill(0));
5
6 const queriesLength = queries.length;
7
8 // Iterate over the range [0, n) for both start and end indices
9 for (let start = 0; start < numLength; ++start) {
10 for (let end = numLength - 1; end >= start; --end) {
11 // If not the first element, update the dp array considering the previous element
12 if (start > 0) {
13 dp[start][end] = Math.max(
14 dp[start][end],
15 dp[start - 1][end] + (nums[start - 1] >= queries[dp[start - 1][end]] ? 1 : 0),
16 );
17 }
18 // If not the last element, update the dp array considering the next element
19 if (end + 1 < numLength) {
20 dp[start][end] = Math.max(
21 dp[start][end],
22 dp[start][end + 1] + (nums[end + 1] >= queries[dp[start][end + 1]] ? 1 : 0),
23 );
24 }
25 // If all queries are processed, return the query count
26 if (dp[start][end] == queriesLength) {
27 return queriesLength;
28 }
29 }
30 }
31
32 // Find the maximum number of queries that can be processed from any single position
33 let maxQueries = 0;
34 for (let index = 0; index < numLength; ++index) {
35 maxQueries = Math.max(maxQueries, dp[index][index] + (nums[index] >= queries[dp[index][index]] ? 1 : 0));
36 }
37
38 // Return the maximum number of queries that can be processed
39 return maxQueries;
40}
41Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is
[3, 7, 40, 80].
What is the recurrence relation?
Time and Space Complexity
Time Complexity
The time complexity of the code is derived from the nested loops it contains. There are two loops each iterating over the length of nums, indexed by i and j. The outer loop runs n times where n is the length of nums. The inner loop runs n times for each iteration of the outer loop, effectively resulting in n * n iterations. Within these loops, the code performs a constant amount of work for each iteration, mainly comparisons and assignments which are O(1) operations.
Therefore, the time complexity is O(n^2).
Space Complexity
The space complexity of the code is determined by the amount of memory used to store variables and data structures. Here, the 2D array f of size n * n is the dominant factor. Since it stores n sublists of length n, the total space used by this array is proportional to n^2. No other data structures in the code use space that is dependent on n in a way that would increase the overall space complexity.
Thus, the space complexity is also O(n^2).
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.