LeetCode 303 – Range Sum Query – Immutable

Problem.

This is a very straight forward rage cache problem since the only required operation is a range summation query.

The way I handle this problem is to cache the sum result between the first every elements and the first element. (I believe most people will do the same.) So that if you want to query the sum from i to j, we just need to return the subtraction between the sum from 0 to j and 0 to i.

sum[i, j] = sum[0, j] – sum[0, i]

The time complexity for this approach will be O(n) for the one time setup and O(1) for each query.

My Code:

public class NumArray {
    int[] sums;
        
    public NumArray(int[] nums) {
        sums = new int[nums.Length];
        if(nums.Length <= 0) return;
        
        sums[0] = nums[0];
        for(int i = 1; i < sums.Length; i++){
            sums[i] = sums[i-1] + nums[i];
        }
    }
    
    public int SumRange(int i, int j) {
        if(i == 0) {return sums[j];}
        else {return sums[j] - sums[i-1];}
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.SumRange(i,j);
 */

Note that I didn’t have boundary check for both i and j in my SumRange function. I would try to point this out to my interviewer if I am asked this problem.

Leave a Reply

Your email address will not be published. Required fields are marked *