This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given an integer array *nums*, find the sum of the elements between indices *i* and *j* (*i* ≤ *j*), inclusive.

**Example:**

Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3

**Note:**

- You may assume that the array does not change.
- There are many calls to
*sumRange*function.

b'

\n## Solution

\n

\n#### Approach #1 (Brute Force) [Time Limit Exceeded]

\n\n

\n#### Approach #2 (Caching) [Accepted]

\n\n

\n#### Approach #3 (Caching) [Accepted]

\n\n

'
\n\n

\n\n

Each time *sumRange* is called, we use a for loop to sum each individual element from index to .

private int[] data;\n\npublic NumArray(int[] nums) {\n data = nums;\n}\n\npublic int sumRange(int i, int j) {\n int sum = 0;\n for (int k = i; k <= j; k++) {\n sum += data[k];\n }\n return sum;\n}\n

**Complexity analysis:**

- \n
- \n
Time complexity : time per query.\nEach

\n*sumRange*query takes time. \n - \n
Space complexity : . Note that

\n`data`

is a*reference*to`nums`

and is not a copy of it. \n

\n

Imagine that *sumRange* is called one thousand times with the exact same arguments. How could we speed that up?

We could trade in extra space for speed. By pre-computing all range sum possibilities and store its results in a hash table, we can speed up the query to constant time.

\nprivate Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();\n\npublic NumArray(int[] nums) {\n for (int i = 0; i < nums.length; i++) {\n int sum = 0;\n for (int j = i; j < nums.length; j++) {\n sum += nums[j];\n map.put(Pair.create(i, j), sum);\n }\n }\n}\n\npublic int sumRange(int i, int j) {\n return map.get(Pair.create(i, j));\n}\n

**Complexity analysis**

- \n
- \n
Time complexity : time per query, time pre-computation.\nThe pre-computation done in the constructor takes time. Each

\n*sumRange*query\'s time complexity is as the hash table\'s look up operation is constant time. \n - \n
Space complexity : .\nThe extra space required is as there are candidates for both and .

\n \n

\n

The above approach takes a lot of space, could we optimize it?

\nImagine that we pre-compute the cummulative sum from index to . Could we use this information to derive ?

\nLet us define as the cumulative sum for (inclusive):

\n\n\n

\nNow, we can calculate *sumRange* as following:

\n\n

\nprivate int[] sum;\n\npublic NumArray(int[] nums) {\n sum = new int[nums.length + 1];\n for (int i = 0; i < nums.length; i++) {\n sum[i + 1] = sum[i] + nums[i];\n }\n}\n\npublic int sumRange(int i, int j) {\n return sum[j + 1] - sum[i];\n}\n

Notice in the code above we inserted a dummy 0 as the first element in the *sum* array. This trick saves us from an extra conditional check in *sumRange* function.

**Complexity analysis**

- \n
- \n
Time complexity : time per query, time pre-computation.\nSince the cumulative sum is cached, each

\n*sumRange*query can be calculated in time. \n - \n
Space complexity : .

\n \n