Range Sum Query - Immutable


  • 0

    Click here to see the full article post


  • 0
    R

    Oh, I find Java support Pair , amazing for me as a C++ developer.


  • 0

    @readonlyfile Well...

    Submission Result: Compile Error
    Line 3: error: cannot find symbol: class Pair


  • 0
    J

    When I run the The Approach #2,the result is :"Compile Error.Line 2: error: cannot find symbol: class pair".
    And I implemented the Approach #2 in C++,the result is:"Time Limit Exceeded.“And the last executed input is a very large number.I want to know why is it?


  • -1
    M

    For the code in Approach #3: There is no dummy element inserted into sum[0]. I believe sum[0] should be set to nums[0], then you can start the for each loop. Also there is no handling in the case where nums is an empty array.


  • 0
    A

    I wonder why no one even mentioned that we should use long long as sum type since we add up a bunch of integers which would be very likely to overflow.
    Besides, in Approach #3, sum[0] is not a dummy. It must be initialized to 0, or you get wrong values all the way up to n.


  • 0
    A

    Alright. Since it is defined as int sumRange(), which means long long can go home and watch it overflow.


  • 0
    W

    @jfyh5388 I have the same error, did you find out how to solve it?


  • 0
    W

    the method 2 has compile error: no class Pair


  • 0
    V

    Solution #2 written in Python doesn't pass the 16th test case: time limit exceeded


  • 0
    C

    #3 is so brillliant!


  • 0
    F
    This post is deleted!

  • -1
    S

    #3 is not robust, because the sum might exceed int max. The test inputs didn't expose this problem though.


  • 0

    @suginanana Please show us an input that does expose this alleged problem.


  • 0
    H

    @StefanPochmann [1,127,128] is a possible case.


  • 0

    @Hughyoung Huh? The sum is nowhere near int max.


  • 0
    S

    JavaScript implementations of the suggested accepted solutions are receiving time limit exceeded. Can anyone advise?

    var NumArray = function(nums) {
        this.cache = {};
        for (var i = 0; i < nums.length; i++) {
           var value = 0;
           for (var j = i; j < nums.length; j++) {
               value += nums[j];
               this.cache[i+":"+j] = value; // create simple string key
           }
        } 
    };
    NumArray.prototype.sumRange = function(i, j) {
        return this.cache[i+":"+j];
    };
    

  • 0
    D

    so brilliant...And speak of the class Pair, how about write one<( ̄︶ ̄)>


  • 0
    G

    i use two-dimensional array instead of pair,but the result is memory limit exceeded.


  • 0
    C

    It is true you can get overflow in the third solution, but this doesn't invalidate the method.
    Let's try an example with an array of 300 entries of 100 million. The sum will obviously overflow, but when calculating sumRange(i, j), we can distinguish two possibilities:

    • the sum doesn't overflow in the interval: sum[i] = actual sum up to i - x * 2^32-1 and sum[j+1] = actual sum up to and including j - x * 2^32-1; when calculating sum[j+1] - sum[i] the overflows will balance out.
    • the sum does overflow in the inteval: sum[i] = actual sum up to i - x * 2^32-1 and sum[j+1] = actual sum up to and including j - (x+1) * 2^32-1; when calculating sum[j+1] - sum[i], this results in the actual result - 2^32-1, which will underflow to the actual result.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.