Clean python solution, one pass


  • 24

    Revised code, 84ms, thanks Stefan !

    def maxSubArrayLen(self, nums, k):
        ans, acc = 0, 0               # answer and the accumulative value of nums
        mp = {0:-1}                 #key is acc value, and value is the index
        for i in xrange(len(nums)):
            acc += nums[i]
            if acc not in mp:
                mp[acc] = i 
            if acc-k in mp:
                ans = max(ans, i-mp[acc-k])
        return ans

  • 3

    Looking for acc+k in mp doesn't make sense. Fortunately mp[acc+k][-1]-i is never positive and thus never wins against ans, though, so it's not wrong but only a waste of time.

    And the repeated mp[acc]+[i] is inefficient, making this an O(n^2) solution only. Try nums = [0] * 10000, for example.


  • 0

    Thank you for pointing out the problems! I have revised my code accordingly.
    But I don't understand why the mp[acc]+[i] makes it an O(n^2) solution. which operation within the for loop takes O(n) time? Please correct me if I am wrong, but I think mp[acc]+[i] is like mp[acc].extend([i]) or mp[acc].append(i), which takes constant time (amortized).


  • 6

    No, + isn't like extend, append or even +=. It creates a new list and thus takes linear time.

    Again, you can easily test it. Just add nums = [0] * 10000 as the first line and click "Run Code". It'll take about 280 ms. Then use

            if acc not in mp:
                mp[acc] = [i]
            else:
                mp[acc] += [i]          <= crucial difference, using "+="
    

    instead of your original line and it'll take about 50 ms (which really is close to zero, considering that Python timing always has about 50 ms overhead here.

    Or just like this:

    >>> from timeit import timeit
    >>> n = 30000
    >>> timeit('x += [1]', 'x = []', number=n)
    0.010766158699491135
    >>> timeit('x = x + [1]', 'x = []', number=n)
    4.195992967101765
    

  • 0

    Thank you for kindly explaining this!

    I never thought arr += [x] and arr = arr + [x] can have such huge difference..


  • 0
    F

    I created a custom test case, this solution gives answer 0, expect answer 10 (exclude 3+5, or exclude 1+7).
    [1,0,2,0,3,4,7,5,6,1,9,22]
    52
    Do I misunderstand somthing?


  • 1

    I tried your test case and it showed that the expected answer is 0, not 10. I think u misunderstood the concept of subarray, which is a consecutive part of the input array. In your example, you cannot exclude 3+5 or 1+7 since your resulting "subarray" would not be consecutive.


  • 0
    D

    Hi, cbmbbz
    Can you explain how the code after second if clause works in your revised code? Thanks.


  • 1

    “if acc-k in mp:” is to find whether there's a subarray with sum of k; and mp[acc-k] has the starting index of that subarry, and thus i-mp[acc-k] is the length of the subarray.


  • 0
    O

    Nice!
    Do you know the difference between append and +=?


  • 2

    why do you choose mp = {0:-1}
    instead of mp = {}


  • 2
    F

    @Zura This way, whenever acc = 0 in your subarray, the value at mp[0] remains -1 instead of being changed to the current index, i. You want to include consecutive values in your subarray that total to 0 in order to get the longest subarray count that sums up to k.

    Take the first example given: nums = [1, -1, 5, -2 , 3] and k = 3. When you use mp = {0:-1} in the beginning, at i = 1, acc = 0. When you reach i = 3, acc = 3. acc - k = 0 and i - mp[acc - k] = 4 (which is the longest subarray length that totals k). If instead mp = {} in the beginning, mp[0] gets updated at i = 1 and, at i = 3, i - mp[acc - k] = 2.


Log in to reply
 

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