https://leetcode.com/problems/range-sum-query-immutable/
The problem is quite trivial if approached with the brute force method. The method I will be conceptualizing is going to include dynamic programming.
We are given an array and two indices. We must the maximum of the range between and including the indices.
If we create an auxillary array that has the sum of all previous indices and the current index, then when we are given two indices to find the max range of, we can simply get the sum of the array at the second index and subtract everything before the intial index and we will be left with the solution.
The indices not included in the range are still contributing to the value of the second index, but they are unnecessary. If they are unnecessary; subtracting them will essentially remove that unnecessary burden they were adding.
The indices after the second index are not contributing any burden and, instead you are contributing to their values.
Keeping the above in mind, the implementation is very elegant and simple.
Space: O(n)
An auxillary array is maintained.
Time: O(n)
We will iterate through the input array once to construct the auxillary array.
You will be able to find the ranges for the indices provided in O(1) time using elementary operations.
Note: The implementation I'm using to construct the auxillary array is not effecient, but lets imagine I didn't want to use .reduce.
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.nums = nums
this.numsAccSums = nums.reduce((acc, curr, idx, array) => [...acc, acc[idx] + array[idx]], [0])
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
const rightIdx = j + 1
const leftIdx = i + 1
console.log(this.numsAccSums)
return this.numsAccSums[rightIdx] - this.numsAccSums[leftIdx - 1]
};
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(i,j)
*/