Implement Prefix Sums and KadaneStep 2 of 5

Subarrays Summing to K

12345

Step 2: Subarrays Summing to K

Now count how many contiguous subarrays sum to a target k. The running prefix sum plus a hashmap of prefix-count solves it in one pass.

Write subarray_sum_equals_k(nums, k):

  • Keep a running prefix sum as you scan.
  • A subarray ending at the current index sums to k exactly when a previous prefix equals (running - k).
  • Store counts of every prefix seen so far in a dict, seeded with {0: 1} so that prefixes equal to k themselves are counted.

This must work with negative numbers, which is why sliding windows do not apply.

Hints
Starter code
class RangeSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def query(self, i, j):
        return self.prefix[j + 1] - self.prefix[i]


def subarray_sum_equals_k(nums, k):
    """Count contiguous subarrays whose sum equals k."""
    # TODO: running prefix sum + dict of prefix counts seeded {0: 1}
    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.

PreviousNext step