Implement Prefix Sums and KadaneStep 1 of 5

Range-Sum Queries

12345

Step 1: Range-Sum Queries

Analytics dashboards ask the same question over and over: what is the sum of a slice of an array? Recomputing it each time is O(n) per query. A prefix-sum array turns every range query into O(1).

Build a class RangeSum:

  • init(self, nums) stores a prefix-sum array. A common trick is to keep a leading zero so that prefix[k] equals the sum of the first k elements.
  • query(self, i, j) returns the sum of nums[i..j] inclusive in O(1).

With a leading-zero prefix, the answer is prefix[j + 1] - prefix[i].

Hints
Starter code
class RangeSum:
    def __init__(self, nums):
        """Build a prefix-sum array from nums."""
        # TODO: build self.prefix (a leading zero makes query simple)
        pass

    def query(self, i, j):
        """Return the sum of nums[i..j] inclusive in O(1)."""
        # TODO: use self.prefix to answer in constant time
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

OverviewNext step