2
\$\begingroup\$

I was solving this challenge on the leetcode site. And my runtime is horrible, it beats only 4% of the other solutions. How can I make this better?

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
   this.nums = nums;
};
/** 
 * @param {number} i 
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function(i, j) {
    let sum = 0;
    for (i; i <= j; i++) {
        sum += this.nums[i];
    }
    return sum;
};

/** 
 * Your NumArray object will be instantiated and called as such:
 * var obj = Object.create(NumArray).createNew(nums)
 * var param_1 = obj.sumRange(i,j)
 */
\$\endgroup\$
  • \$\begingroup\$ Possible duplicate of Play With Numbers Programming Challenge (mean value of subarrays) \$\endgroup\$ – Acccumulation Dec 7 '17 at 20:31
  • \$\begingroup\$ @Acccumulation I wouldn't say it's a duplicate. This is javascript and the other quesiton is c++. From the algorithmic point of view one could say they might be duplicates but as far as the programming languages are concerned they are quite different. \$\endgroup\$ – t3chb0t Dec 7 '17 at 22:54
  • \$\begingroup\$ @Acccumulation That's not how duplicates work at Code Review. Please read the relevant meta discussion. \$\endgroup\$ – Mast Dec 8 '17 at 0:12
4
\$\begingroup\$

While your code is neat, and organized, the issue is with your algorithm.

The simple fact is that you only need to loop through the nums array once, when you create the NumArray instance. The trick is to "memoize" the sum of all members to one side of the array, and then compute the difference when looking for the sum later.

Consider the code:

var NumArray = function(nums) {
    this.nums = nums;
    this.sums = [];
    let sofar = 0;
    for (let i = 0; i < this.nums.length; i++) {
        this.sums.push(sofar);
        sofar += this.nums[i];
    }
};

NumArray.prototype.sumRange = function(i, j) {
    return this.sums[j] - this.sums[i] + this.nums[j];
};

Note how this.sums is the sum of all memebers to the left of i, and then sumRange just needs to find the difference.

Remember, optimization often involves solving expensive problems fewer times, and reusing the results of the expensive calculation to derive other answers.

As for your code, the LeetCode Javascript format is not a great one for good code quality..... but your use is simple enough to not have any real issues.

Try it out here:

var NumArray = function(nums) {
    this.nums = nums;
    this.sums = [];
    let sofar = 0;
    for (let i = 0; i < this.nums.length; i++) {
        this.sums.push(sofar);
        sofar += this.nums[i];
    }
};

NumArray.prototype.sumRange = function(i, j) {
    return this.sums[j] - this.sums[i] + this.nums[j];
};

/** 
 * Your NumArray object will be instantiated and called as such:
 * var obj = Object.create(NumArray).createNew(nums)
 * var param_1 = obj.sumRange(i,j)
 */

const nums = [-2, 0, 3, -5, 2, -1];
var obj = new NumArray(nums);

const results = document.getElementById('results');
function getSum(i, j) {
  const sum = obj.sumRange(i,j);
  results.innerHTML += `From ${i} to ${j} the sum is ${sum}\n`;
}
results.innerHTML += `${obj.sums}\n`;
getSum(0, 2);
getSum(2, 5);
getSum(0, 5);
<pre id='results'>Results
</pre>

\$\endgroup\$
1
\$\begingroup\$

Runtime Complexity

As pointed out by others, your implementation performs a summation over elements in range [i, j] per lookup in linear time. You can improve the runtime complexity as follows:

  1. Compute and store the zero-padded cumulative sum such that cumsum[i] is the sum of all nums from 0 to i - 1:

      nums =    [1, 1, 1, 1, 1]
    cumsum = [0, 1, 2, 3, 4, 5]
    
  2. Compute any sum of range [i, j] by subtracting cumsum[i] from cumsum[j + 1]. Each lookup now performs just two array lookups and a subtraction in constant time.

Minimal Implementation

const NumArray = function(nums) {
    let sum = 0;
    this._cumsum = nums.reduce((acc, num) => (acc.push(sum += num), acc), [0]);
};

NumArray.prototype.sumRange = function(i, j) {
    return this._cumsum[j + 1] - this._cumsum[i];
};

I used the _underscore naming convention to mark private properties. See Managing the private data of ES6 classes for alternatives.

PS: Be aware that some platforms such as leetcode measure execution time on possibly older JavaScript engines and sometimes report timeouts when using newer language features. In such cases, use e.g. a traditional for-loop instead of reduce. Also, it has been reported that measured execution time on leetcode is unreliable and easily varies by more than 50 percentage points per measurement.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.