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 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 themaximum number of queries that can be processed by doing the operation optimally.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8
9

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] <= 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

  1. For every possible subarray [l, r] of nums (where l <= r), treat it as the chosen subsequence.
  2. 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.
  3. Track the maximum number of queries processed over all possible subarrays.
  4. Return the maximum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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 to m queries.
  • 🧺 Space complexity: O(1) — Only a constant amount of extra space is used for pointers and counters.