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:
Each time sumRange is called, we use a for loop to sum each individual element from index to .
private int[] data; public NumArray(int[] nums) { data = nums; } public int sumRange(int i, int j) { int sum = 0; for (int k = i; k <= j; k++) { sum += data[k]; } return sum; }
Complexity analysis:
Time complexity : time per query. Each sumRange query takes time.
Space complexity : . Note that data
is a reference to nums
and is not a copy of it.
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.
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>(); public NumArray(int[] nums) { for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; map.put(Pair.create(i, j), sum); } } } public int sumRange(int i, int j) { return map.get(Pair.create(i, j)); }
Complexity analysis
Time complexity : time per query, time pre-computation. The pre-computation done in the constructor takes time. Each sumRange query's time complexity is as the hash table's look up operation is constant time.
Space complexity : . The extra space required is as there are candidates for both and .
The above approach takes a lot of space, could we optimize it?
Imagine that we pre-compute the cummulative sum from index to . Could we use this information to derive ?
Let us define as the cumulative sum for (inclusive):
Now, we can calculate sumRange as following:
private int[] sum; public NumArray(int[] nums) { sum = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { sum[i + 1] = sum[i] + nums[i]; } } public int sumRange(int i, int j) { return sum[j + 1] - sum[i]; }
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
Time complexity : time per query, time pre-computation. Since the cumulative sum is cached, each sumRange query can be calculated in time.
Space complexity : .