DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Range Sum Query - Immutable

Problem
TC: O(n) for calculating the prefix sum and O(1) for getting the sum of the subarray in the range left and right

class NumArray {

    int prefix[];
    public NumArray(int[] nums) {
        prefix = new int[nums.length];
        int currentSum =0;
        for(int i=0;i<nums.length;i++){
            currentSum+=nums[i];
            prefix[i] = currentSum;
        }
    }

    public int sumRange(int left, int right) {
        int rightSum = prefix[right];
        int leftSum = (left>0) ? prefix[left-1]:0;
        return rightSum-leftSum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */
Enter fullscreen mode Exit fullscreen mode

For calculating the sum of the subarray within left and right we can leverage the prefix sum, each prefix[i] tell the sum till ith index from the starting index 0, hence if we have to find the sum of subarray left and right (inclusive) can get the rightPrefixSum till right index( it will be from 0 to right index) and we can also get leftPrefixSum till left-1 (it will be from 0 to left-1 index) and finally when we do rightPrefixSum-leftPrefixSum we will get the sum of subarray between left and right pointer.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay