Scale Engineer

Maximum Sum Queries

Hard
#2462Time: O(n * q), where `n` is the length of `nums1`/`nums2` and `q` is the number of queries. For each of the `q` queries, we iterate through `n` elements.Space: O(q) to store the answer array. If the output array is not considered, the space complexity is O(1).
Algorithms
Binary SearchSorting
Data structures
ArrayStackMonotonic StackBinary Indexed TreeSegment Tree

Prompt

You are given two 0-indexed integer arrays nums1 and nums2, each of length n, and a 1-indexed 2D array queries where queries[i] = [xi, yi].

For the ith query, find the maximum value of nums1[j] + nums2[j] among all indices j (0 <= j < n), where nums1[j] >= xi and nums2[j] >= yi, or -1 if there is no j satisfying the constraints.

Return an array answer where answer[i] is the answer to the ith query.

 

Example 1:

x<sub>i</sub> = 4

Example 2:

j = 2

Example 3:

x<sub>i</sub>

 

Constraints:

  • nums1.length == nums2.length 
  • n == nums1.length 
  • 1 <= n <= 105
  • 1 <= nums1[i], nums2[i] <= 109 
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • xi == queries[i][1]
  • yi == queries[i][2]
  • 1 <= xi, yi <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

The most straightforward solution is to iterate through all the given numbers for each query. For every query (x, y), we check every pair (nums1[j], nums2[j]) to see if it satisfies the conditions nums1[j] >= x and nums2[j] >= y. We keep track of the maximum sum nums1[j] + nums2[j] found among all valid pairs.

Algorithm

    1. Initialize an answer array of size q (number of queries) with -1.
    1. For each query i from 0 to q-1 with [x, y]:
    1. Initialize max_sum = -1.
    1. For each index j from 0 to n-1:
    1. If `nums1[j] >= x` and `nums2[j] >= y`:
    1. Update `max_sum = max(max_sum, nums1[j] + nums2[j])`.
    1. Set answer[i] = max_sum.
    1. Return answer.

Walkthrough

We initialize an answer array for all queries with a default value of -1. We then loop through each query (xi, yi). Inside this loop, we start another loop that iterates through all indices j from 0 to n-1. For each index j, we perform a check: if (nums1[j] >= xi && nums2[j] >= yi). If the condition is true, we calculate the sum s = nums1[j] + nums2[j] and update the maximum sum for the current query: answer[i] = max(answer[i], s). After checking all j for a given query i, answer[i] will hold the required maximum sum, or -1 if no valid pair was found. This process is repeated for all queries.

class Solution {    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {        int n = nums1.length;        int q = queries.length;        int[] answer = new int[q];         for (int i = 0; i < q; i++) {            int x = queries[i][0];            int y = queries[i][1];            int maxSum = -1;            for (int j = 0; j < n; j++) {                if (nums1[j] >= x && nums2[j] >= y) {                    maxSum = Math.max(maxSum, nums1[j] + nums2[j]);                }            }            answer[i] = maxSum;        }        return answer;    }}

Complexity

Time

O(n * q), where `n` is the length of `nums1`/`nums2` and `q` is the number of queries. For each of the `q` queries, we iterate through `n` elements.

Space

O(q) to store the answer array. If the output array is not considered, the space complexity is O(1).

Trade-offs

Pros

  • Very simple to understand and implement.

  • Requires no complex data structures.

Cons

  • Highly inefficient. The nested loops lead to a quadratic time complexity in the worst case.

  • Will result in a "Time Limit Exceeded" (TLE) error for large inputs as per the problem constraints.

Solutions

class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; Arrays . fill ( c , - 1 ); } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] = Math . max ( c [ x ], v ); x += x & - x ; } } public int query ( int x ) { int mx = - 1 ; while ( x > 0 ) { mx = Math . max ( mx , c [ x ]); x -= x & - x ; } return mx ; } } class Solution { public int [] maximumSumQueries ( int [] nums1 , int [] nums2 , int [][] queries ) { int n = nums1 . length ; int [][] nums = new int [ n ][ 0 ]; for ( int i = 0 ; i < n ; ++ i ) { nums [ i ] = new int [] { nums1 [ i ], nums2 [ i ]}; } Arrays . sort ( nums , ( a , b ) -> b [ 0 ] - a [ 0 ]); Arrays . sort ( nums2 ); int m = queries . length ; Integer [] idx = new Integer [ m ]; for ( int i = 0 ; i < m ; ++ i ) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> queries [ j ][ 0 ] - queries [ i ][ 0 ]); int [] ans = new int [ m ]; int j = 0 ; BinaryIndexedTree tree = new BinaryIndexedTree ( n ); for ( int i : idx ) { int x = queries [ i ][ 0 ], y = queries [ i ][ 1 ]; for (; j < n && nums [ j ][ 0 ] >= x ; ++ j ) { int k = n - Arrays . binarySearch ( nums2 , nums [ j ][ 1 ]); tree . update ( k , nums [ j ][ 0 ] + nums [ j ][ 1 ]); } int p = Arrays . binarySearch ( nums2 , y ); int k = p >= 0 ? n - p : n + p + 1 ; ans [ i ] = tree . query ( k ); } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem