Skip to content
ComplexityX

Settings

Server engine

Loading…

Use my own key optional

The key stays in this browser's local storage and is sent only to this app's /api/analyze route, which forwards it to the provider. It is never stored on the server.

All patterns

Prefix Sum

Precompute running totals so any range sum is a subtraction.

time O(n)space O(n)

What it is

Let P[i] be the sum of the first i elements. Then sum(l..r) = P[r+1] − P[l]. Combined with a HashMap of earlier prefixes it solves range-sum-equals-k problems even with negative numbers.

When to reach for it

  • Many range sum queries
  • Subarray with sum k, divisible by k, or balanced counts
  • 2D region sums

Clues in the problem

  • Inner loop re-adds a range each time
  • Negative numbers rule out sliding window

Template

def count_subarrays(a, k):
seen = {0: 1} # prefix -> how many times
pref = ans = 0
for x in a:
pref += x
ans += seen.get(pref - k, 0)
seen[pref] = seen.get(pref, 0) + 1
return ans

Practice problems

  • Subarray Sum Equals K
  • Range Sum Query
  • Contiguous Array
  • Product of Array Except Self

Common mistakes

  • Forgetting the empty prefix {0: 1}
  • Integer overflow in prefix totals
  • Off-by-one between P[r+1] and P[r]