Sqrt buckets python 100ms

  • 0

    O(1) to update() and O(sqrt(n)) to sumRange(). Originally I stored all the cumulative sums of and within each bucket, which made it O(1) to sumRange() and O(sqrt(n)) to update() and ran slower on the test cases given.

    class NumArray(object):
        def __init__(self, nums):
            self.width = int(len(nums)**0.5)    # width of each bin (apart from last)
            self.bin_sums = []                  # sum of each bin
            self.nums = nums
            for i, num in enumerate(nums):
                if i % self.width == 0:         # start a new bin
                else:                           # add to last bin
                    self.bin_sums[-1] += num
        def update(self, i, val):
            bin_i = i // self.width
            diff = val - self.nums[i]
            self.bin_sums[bin_i] += diff        # update bin_sums
            self.nums[i] = val                  # update nums
        def sumRange(self, i, j):
            bin_i, bin_j = i // self.width, j // self.width
            range_sum = sum(self.bin_sums[bin_i:bin_j])         # sum of whole bins 
            range_sum += sum(self.nums[bin_j*self.width:j+1])   # add partial last bin
            range_sum -= sum(self.nums[bin_i*self.width:i])     # subtract partial first bin
            return range_sum

Log in to reply

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