I do not understand why a legitimate O(n) solution is not accepted.


  • 0
    S
    class NumArray(object):
        def __init__(self, nums):
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            self.nums = nums
            
    
        def sumRange(self, i, j):
            """
            sum of elements nums[i..j], inclusive.
            :type i: int
            :type j: int
            :rtype: int
            """
            sum = 0
            for k in range(i,j+1):
                sum += self.nums[k]
            return sum
    
    
    # Your NumArray object will be instantiated and called as such:
    # numArray = NumArray(nums)
    # numArray.sumRange(0, 1)
    # numArray.sumRange(1, 2)

  • 1
    S

    Never mind. I understood the reason why they needed to optimize. Multiple calls to my previous method would have been O(n) each.

    class NumArray(object):
        def __init__(self, nums):
            """
            initialize your data structure here.
            :type nums: List[int]
            """
            sumArr = [0] * len(nums)
            if len(nums) > 0:
                sumArr[0] = nums[0]
            for i in range(1,len(nums)):
                sumArr[i] = nums[i] + sumArr[i-1]
            self.sum = sumArr
            
    
        def sumRange(self, i, j):
            """
            sum of elements nums[i..j], inclusive.
            :type i: int
            :type j: int
            :rtype: int
            """
            if i == 0:
                return self.sum[j]
            else:
                return self.sum[j] - self.sum[i-1]
    
    
    # Your NumArray object will be instantiated and called as such:
    # numArray = NumArray(nums)
    # numArray.sumRange(0, 1)
    # numArray.sumRange(1, 2)

  • 0
    K

    Yep, move the complexity to the initialization (because you only need to initialize once) and simplify the sumRange method since it will be called many times~


Log in to reply
 

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