Prefix sums & hashmap counting

Precompute once, answer in O(1). Two ideas that constantly combine to turn O(n²) scans into O(n): a range is the difference of two prefixes, and a hashmap turns "search all left endpoints" into "look up a single key."

Why this pattern

Two ideas that constantly combine to turn O(n²) scans into O(n):

1. Prefix sums. Precompute P[i] = a[0] + … + a[i-1] (with P[0] = 0). Then ANY range sum is a single subtraction: sum(a[l..r]) = P[r+1] - P[l]. Build P in O(n); each query is O(1). The reusable identity is the whole trick: a range is the difference of two prefixes.
2. Hashmap counting. A dict gives O(1) average lookup of "have I seen X?" or "how many times have I seen X?". Combined with prefix sums it answers subarray questions in one pass instead of checking all O(n²) ranges.

The centerpiece: subarray sum equals K (why the hashmap is magic)

We want the number of contiguous subarrays summing to K. Brute force tries all O(n²) [l, r] pairs. But using prefixes:

sum(a[l..r]) == K   <=>   P[r+1] - P[l] == K   <=>   P[l] == P[r+1] - K

So as we sweep r and maintain the running prefix cur = P[r+1], the number of valid left endpoints is exactly "how many earlier prefixes equal cur - K." A hashmap of {prefix_value -> count_seen_so_far} answers that in O(1). We sweep once ⇒ O(n). The hashmap converts "search all left endpoints" into "look up a single key" — that is the entire n² → n collapse.

Prefix sums

LeetCode 303 — Range Sum Query (immutable)

Precompute prefix sums once; answer sum(l..r) in O(1) per query. P[i] = sum of first i elements; sum(l..r) = P[r+1] - P[l].

class RangeSum:
    def __init__(self, a: List[int]):
        self.P = [0] * (len(a) + 1)              # P[0] = 0 (empty prefix)
        for i, x in enumerate(a):
            self.P[i + 1] = self.P[i] + x
    def query(self, l: int, r: int) -> int:      # inclusive [l, r]
        return self.P[r + 1] - self.P[l]

LeetCode 560 — Subarray Sum Equals K

Count contiguous subarrays summing to k (handles negatives — this is why a sliding window can't be used). A subarray (l..r] sums to k iff P[r+1] - P[l] == k iff P[l] == cur - k. Maintain counts of prefix values seen so far; at each r add how many earlier prefixes equal cur - k.

def subarray_sum_equals_k(a: List[int], k: int) -> int:
    seen = {0: 1}                # empty prefix, so subarrays starting at 0 count
    cur = 0
    total = 0
    for x in a:
        cur += x
        total += seen.get(cur - k, 0)   # earlier prefixes that complete a k-sum
        seen[cur] = seen.get(cur, 0) + 1
    return total

LeetCode 238 — Product of Array Except Self

No division; O(n) time. It's the prefix-sum idea but multiplicative. ans[i] = (product of everything left of i) * (product of everything right of i). First pass fills left-products; second pass multiplies in right-products using a single running variable, so only O(1) extra space beyond the output.

def product_except_self(a: List[int]) -> List[int]:
    n = len(a)
    ans = [1] * n
    for i in range(1, n):                # ans[i] = product of a[0..i-1]
        ans[i] = ans[i - 1] * a[i - 1]
    right = 1
    for i in range(n - 1, -1, -1):       # fold in product of a[i+1..n-1]
        ans[i] *= right
        right *= a[i]
    return ans

LeetCode 304 — Range Sum Query 2D (inclusion-exclusion)

Sum the submatrix with corners (r1,c1)..(r2,c2) inclusive. Build a 2D prefix P where P[i][j] = sum of the rectangle from (0,0) to (i-1,j-1). Then the submatrix sum is inclusion-exclusion:

P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

(subtract the top and left strips, add back the doubly-removed corner.)

def matrix_region_sum(matrix: List[List[int]], r1: int, c1: int,
                      r2: int, c2: int) -> int:
    R, C = len(matrix), len(matrix[0])
    P = [[0] * (C + 1) for _ in range(R + 1)]
    for i in range(R):
        for j in range(C):
            P[i + 1][j + 1] = (matrix[i][j] + P[i][j + 1]
                               + P[i + 1][j] - P[i][j])
    return (P[r2 + 1][c2 + 1] - P[r1][c2 + 1]
            - P[r2 + 1][c1] + P[r1][c1])

Difference arrays (the dual of prefix sums)

Prefix sums answer range queries cheaply. Difference arrays answer range updates cheaply: to add v to a[l..r], do diff[l] += v and diff[r+1] -= v in O(1); a final prefix-sum pass over diff reconstructs the array. m updates + O(n) finalize = O(n + m) instead of O(n·m).

def range_add(n: int, updates: List[List[int]]) -> List[int]:
    diff = [0] * (n + 1)
    for l, r, v in updates:
        diff[l] += v
        diff[r + 1] -= v          # cancel the increment just past the range
    out = [0] * n
    run = 0
    for i in range(n):
        run += diff[i]            # prefix-sum the deltas -> actual values
        out[i] = run
    return out

The other hashing workhorses

LeetCode 1 — Two Sum (unsorted)

Return indices of the pair summing to target. For each x we need a previously-seen partner == target - x. A hashmap {value -> index} answers that in O(1), so one pass suffices instead of O(n²) pair checks. (Contrast lesson 05's two-pointer version, which needs a sorted array; this version needs none.)

def two_sum(nums: List[int], target: int) -> List[int]:
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

LeetCode 49 — Group Anagrams

Two strings are anagrams iff their sorted letters match. Use that sorted tuple as a CANONICAL KEY in a dict; words collide into the same bucket iff they're anagrams. O(1) bucket lookup avoids O(n²) pairwise comparisons.

def group_anagrams(words: List[str]) -> List[List[str]]:
    buckets = {}
    for w in words:
        key = "".join(sorted(w))
        buckets.setdefault(key, []).append(w)
    return list(buckets.values())

LeetCode 128 — Longest Consecutive Sequence

O(n), unsorted input. Put everything in a set for O(1) membership. Only START counting a run at a value x whose predecessor x-1 is ABSENT (so x is a sequence start). Then walk x, x+1, x+2…. Each element is visited by an inner walk at most once across the whole run, giving O(n) despite the nested loop.

def longest_consecutive(nums: List[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:               # x is the start of its run
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best

LeetCode 387 — First Unique Character in a String

Return its index, else -1. A count map gives each char's frequency in one pass; a second pass returns the first index whose count is 1. Two O(n) passes, O(1) space (alphabet bounded).

def first_uniq_char(s: str) -> int:
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if count[ch] == 1:
            return i
    return -1

LeetCode 217 — Contains Duplicate

A seen-set detects a repeat the instant it occurs, short-circuiting before scanning the rest. (len(set) != len(list) is a one-liner but always scans everything.)

def contains_duplicate(nums: List[int]) -> bool:
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False