303. Range Sum Query

Problem Statement in English

You’re given an array nums. The question will provide you with range queries that you must answer. So they give you a left and right index, and you need to return the sum of elements in that range (upper and lower bound inclusive).

Approach

The naive approach is to use a loop for every query that they give you, and start from left, and go towards right, and just just keep adding to a sum variable. But this has a time complexity of $O(n)$, and we can do better. We can bring it down to constant time. Let’s see how.

We use a technique called Prefix Sums. In this technique, we build a sort of auxilliary lookup table. We build this table beforehand, and that way whenever a query comes in, we can check the lookup table and return an answer on constant time. Now, how do we build this lookup table?

To make range queries a constant time operation, we need to ensure that when a query comes in there’s no calculation to do. It has to be a direct read. So we build this lookup table when the initial array is provided. I’m going to give an example:

So you see how it’s built? We keep using the previous computation and just add the current cell to it.

Solution in Python

class NumArray:

    def __init__(self, nums: List[int]):
        # initialise index with first element
        self.index = [nums[0]]

        # build index from index 1
        for i in range(1, len(nums)):
            # use the previously computed value in the next calculation
            self.index.append(self.index[-1] + nums[i])

    def sumRange(self, left: int, right: int) -> int:
        # if it's from 0, then we can directly use the range query until right
        if left == 0:
            return self.index[right]
        else:
            # else remove the sum until the desired starting index
            return self.index[right] - self.index[left - 1]

Complexity

• Time: $O(n)$, $O(1)$
  $O(n)$ to build the index, and the queries themselves are constant time.

• Space: $O(n)$
  Since we store an index that contains $n$ elements at most.

And we are done.