Maximum sum queries

Array Binary Search Stack Binary Indexed Tree Segment Tree Sorting Monotonic Stack

29.9% acceptance

Feb 25, 2026

351

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_sum_queries(
    nums1: Vec<i32>,
    nums2: Vec<i32>,
    queries: Vec<Vec<i32>>,
  ) -> Vec<i32> {
    let n = nums1.len();
    let q = queries.len();

    // Sort pairs by nums1 descending
    let mut pairs: Vec<(i32, i32)> = nums1.into_iter().zip(nums2.into_iter()).collect();
    pairs.sort_by(|a, b| b.0.cmp(&a.0));

    // Sort queries by xi descending, keep original index
    let mut sorted_q: Vec<(i32, i32, usize)> = queries
      .iter()
      .enumerate()
      .map(|(i, q)| (q[0], q[1], i))
      .collect();
    sorted_q.sort_by(|a, b| b.0.cmp(&a.0));

    let mut ans = vec![-1i32; q];
    // BTreeMap: key=nums2[j], value=sum[j]. Maintained as Pareto-optimal:
    // keys ascending → values strictly decreasing (only keep non-dominated points)
    let mut map: std::collections::BTreeMap<i32, i32> = std::collections::BTreeMap::new();
    let mut ptr = 0;

    for (xi, yi, qi) in sorted_q {
      // Add all pairs with nums1 >= xi
      while ptr < n && pairs[ptr].0 >= xi {
        let (n1, n2) = pairs[ptr];
        let s = n1 + n2;
        // Check if dominated: exists entry with key >= n2 and val >= s
        let dominated = map.range(n2..).next().map_or(false, |(_, v)| *v >= s);
        if !dominated {
          // Remove entries with key < n2 and value <= s (now dominated)
          let to_remove: Vec<i32> = map
            .range(..n2)
            .filter(|(_, v)| **v <= s)
            .map(|(k, _)| *k)
            .collect();
          for k in to_remove { map.remove(&k); }
          map.insert(n2, s);
        }
        ptr += 1;
      }
      // For query yi: smallest key >= yi (since values decrease as keys increase)
      if let Some((_, v)) = map.range(yi..).next() {
        ans[qi] = *v;
      }
    }
    ans
  }
}