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

• ``````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)``````

• 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)``````

• 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~

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