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.