Range Sum Query - Immutable

LeetCode 303 | Difficulty: Easy

Easy

Problem Description

Given an integer array nums, handle multiple queries of the following type:

- Calculate the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** where `left <= right`.

Implement the NumArray class:

- `NumArray(int[] nums)` Initializes the object with the integer array `nums`.

- `int sumRange(int left, int right)` Returns the **sum** of the elements of `nums` between indices `left` and `right` **inclusive** (i.e. `nums[left] + nums[left + 1] + ... + nums[right]`).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

Constraints:

- `1 <= nums.length <= 10^4`

- `-10^5 <= nums[i] <= 10^5`

- `0 <= left <= right < nums.length`

- At most `10^4` calls will be made to `sumRange`.

Topics: Array, Design, Prefix Sum

---

Approach

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 164 ms)

Metric	Value
Runtime	164 ms
Memory	35.9 MB
Date	2020-02-08

Solution

public class NumArray {

    int[] dp;
    public NumArray(int[] nums)
    {
        dp = new int[nums.Length+1];
        for (int i = 0; i < nums.Length; i++)
        {
            dp[i+1] = dp[i]+nums[i];
        }
    }

    public int SumRange(int i, int j)
    {
        return dp[j+1] - dp[i] ;
    }
}

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

---

Complexity Analysis

Approach	Time	Space
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Clarify the expected time complexity for each operation before choosing data structures.