Optimize the code · Medium

Speed Up Range Sum Queries

Medium Make it fast Seen at Google, Bloomberg

maxRangeSum(nums, lefts, rights) answers many range queries. Query i covers the indices between lefts[i] and rights[i] inclusive (in either order). Return the largest of the query sums.

The version below adds up every range from scratch. With 80,000 numbers and 80,000 queries it is far too slow. Make it fast without changing the results.

Example 1

Input: nums = [3, -1, 4, 1], lefts = [0, 3], rights = [2, 1]
Output: 6
Explanation: Query 0 sums indices 0..2 = 6; query 1 sums indices 1..3 = 4.

Constraints

1 <= lefts.length == rights.length
0 <= lefts[i], rights[i] < nums.length

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

function maxRangeSum(nums, lefts, rights) {
  let best = -Infinity;
  for (let q = 0; q < lefts.length; q++) {
    const lo = Math.min(lefts[q], rights[q]);
    const hi = Math.max(lefts[q], rights[q]);
    let sum = 0;
    for (let i = lo; i <= hi; i++) sum += nums[i];
    best = Math.max(best, sum);
  }
  return best;
}

function maxRangeSum(nums: number[], lefts: number[], rights: number[]): number {
  let best = -Infinity;
  for (let q = 0; q < lefts.length; q++) {
    const lo = Math.min(lefts[q], rights[q]);
    const hi = Math.max(lefts[q], rights[q]);
    let sum = 0;
    for (let i = lo; i <= hi; i++) sum += nums[i];
    best = Math.max(best, sum);
  }
  return best;
}

def max_range_sum(nums: list[int], lefts: list[int], rights: list[int]) -> int:
    best = None
    for a, b in zip(lefts, rights):
        lo, hi = min(a, b), max(a, b)
        total = 0
        for i in range(lo, hi + 1):
            total += nums[i]
        best = total if best is None else max(best, total)
    return best

<?php

function maxRangeSum(array $nums, array $lefts, array $rights): int
{
    $best = PHP_INT_MIN;
    foreach ($lefts as $q => $a) {
        $lo = min($a, $rights[$q]);
        $hi = max($a, $rights[$q]);
        $sum = 0;
        for ($i = $lo; $i <= $hi; $i++) {
            $sum += $nums[$i];
        }
        $best = max($best, $sum);
    }
    return $best;
}

class Solution {
    public int maxRangeSum(int[] nums, int[] lefts, int[] rights) {
        int best = Integer.MIN_VALUE;
        for (int q = 0; q < lefts.length; q++) {
            int lo = Math.min(lefts[q], rights[q]);
            int hi = Math.max(lefts[q], rights[q]);
            int sum = 0;
            for (int i = lo; i <= hi; i++) sum += nums[i];
            best = Math.max(best, sum);
        }
        return best;
    }
}

Hints

Hint 1

What is the sum of nums[l..r] in terms of the sums of two prefixes?

Hint 2

Build prefix[i] = nums[0] + ... + nums[i - 1] once.

Make it faster

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n + q) · Space O(n)

Why it is slow: each query loops over its range, so the cost is O(q x average range length), here around 2 billion additions.

The fix: precompute prefix sums once: prefix[0] = 0, prefix[i + 1] = prefix[i] + nums[i]. Then the sum of nums[l..r] is prefix[r + 1] - prefix[l], O(1) per query. Total work O(n + q).

Prefix sums are the go-to answer whenever the data is static and the same kind of range aggregate is asked many times. When values change between queries, the follow-up answer is a Fenwick (binary indexed) tree or a segment tree.

Optimized solution

function maxRangeSum(nums, lefts, rights) {
  const prefix = new Array(nums.length + 1);
  prefix[0] = 0;
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  let best = -Infinity;
  for (let q = 0; q < lefts.length; q++) {
    const lo = Math.min(lefts[q], rights[q]);
    const hi = Math.max(lefts[q], rights[q]);
    best = Math.max(best, prefix[hi + 1] - prefix[lo]);
  }
  return best;
}

function maxRangeSum(nums: number[], lefts: number[], rights: number[]): number {
  const prefix: number[] = [0];
  for (let i = 0; i < nums.length; i++) prefix.push(prefix[i] + nums[i]);
  let best = -Infinity;
  for (let q = 0; q < lefts.length; q++) {
    const lo = Math.min(lefts[q], rights[q]);
    const hi = Math.max(lefts[q], rights[q]);
    best = Math.max(best, prefix[hi + 1] - prefix[lo]);
  }
  return best;
}

from itertools import accumulate

def max_range_sum(nums: list[int], lefts: list[int], rights: list[int]) -> int:
    prefix = [0, *accumulate(nums)]  # prefix[i] = sum(nums[:i])
    return max(prefix[max(a, b) + 1] - prefix[min(a, b)] for a, b in zip(lefts, rights))

<?php

function maxRangeSum(array $nums, array $lefts, array $rights): int
{
    $prefix = [0];
    foreach ($nums as $i => $x) {
        $prefix[] = $prefix[$i] + $x;
    }
    $best = PHP_INT_MIN;
    foreach ($lefts as $q => $a) {
        $lo = min($a, $rights[$q]);
        $hi = max($a, $rights[$q]);
        $best = max($best, $prefix[$hi + 1] - $prefix[$lo]);
    }
    return $best;
}

class Solution {
    public int maxRangeSum(int[] nums, int[] lefts, int[] rights) {
        int[] prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
        int best = Integer.MIN_VALUE;
        for (int q = 0; q < lefts.length; q++) {
            int lo = Math.min(lefts[q], rights[q]);
            int hi = Math.max(lefts[q], rights[q]);
            best = Math.max(best, prefix[hi + 1] - prefix[lo]);
        }
        return best;
    }
}

Common mistakes

Off-by-one in the prefix indices: prefix has n + 1 entries.
Forgetting that a query may give its ends in reverse order.

Follow-up questions

Values are updated between queries (Fenwick tree).
2-D version: sums over sub-rectangles of a matrix.

Speed Up Contains Duplicate · Easy
Speed Up Two Sum · Easy
Speed Up Recursive Fibonacci · Easy
Speed Up the Most Frequent Word · Easy
Speed Up the Active-Customer Join · Easy
Speed Up Longest Consecutive Sequence · Medium