3018. Maximum Number of Removal Queries That Can Be Processed I

HardArrayDynamic Programming
Leetcode Link

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:

  1. You can initially choose to replace nums with any of its subsequences. This operation is optional and can be performed only once.

  2. Each element in queries is 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.

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.

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:

  1. Iterate over all possible subarrays of nums by using two nested loops. The outer loop variable i refers to the beginning of the subarray, and the inner loop variable j (which starts from n - 1 and moves backwards to i) refers to the end of the subarray.

  2. At each iteration (i, j), we try to update f[i][j] using two possible actions:

    • If we remove the first element of the subarray (nums[i - 1] when i > 0), we consider the value in f[i - 1][j], as this represents the maximum number of queries processed when nums[i - 1] is included. If nums[i - 1] is greater than or equal to the current query (indicated by queries[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] when j + 1 < n), we consider the value in f[i][j + 1]. Again, if nums[j + 1] satisfies the current query, the value of f[i][j] can be incremented.

  3. During the iteration, if at any point f[i][j] equals m, the total number of queries, we know that we can process all the queries. Thus, we return m immediately, as it's the maximum possible.

  4. 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 all i from 0 to n - 1. We add 1 to f[i][i] if nums[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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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:

  1. 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 set f[1][3] to 1, as we have processed one query.

  2. 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 set f[2][3] to 2, as we have processed another query.

  3. Now the subarray i=2, j=3 is [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], and f[3][3] is set to 3.

  4. As our subarray i=3, j=3 is 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))
38
1class 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}
41
1class 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};
40
1function 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}
41

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many times is a tree node visited in a depth first search?

Recommended Readings

Dynamic Programming Introduction and Patterns

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

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More