# Prefix Sums — Part 2: Interview Problems

Six problems: range queries, the prefix + hash map family (counting, longest, divisibility), and 2D prefix sums.

## 1. Range Sum Query – Immutable (LeetCode 303)

**🟢 Easy.** Design `NumArray(nums)` with `sumRange(left, right)` returning the inclusive range sum. Many queries will be made.

```text
nums = [-2,0,3,-5,2,-1]
sumRange(0,2) → 1 · sumRange(2,5) → -1 · sumRange(0,5) → -3
```

**Approach.** Precompute the prefix array once in the constructor; each query is one subtraction.

**Complexity.** O(n) build, O(1) per query, O(n) space.

```typescript
class NumArray {
  private prefix: number[] = [0];
  constructor(nums: number[]) {
    for (const x of nums) this.prefix.push(this.prefix[this.prefix.length - 1] + x);
  }
  sumRange(left: number, right: number): number {
    return this.prefix[right + 1] - this.prefix[left];
  }
}
```

```python
class NumArray:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]
```

## 2. Find Pivot Index (LeetCode 724)

**🟢 Easy.** Return the leftmost index where the sum of elements to its left equals the sum to its right (−1 if none).

```text
nums = [1,7,3,6,5,6] → 3   (1+7+3 = 5+6)
```

**Approach.** With `total` known, the right sum at i is `total − leftSum − nums[i]`. Walk once, maintaining `leftSum`.

**Complexity.** O(n) time, O(1) space.

```typescript
function pivotIndex(nums: number[]): number {
  const total = nums.reduce((a, b) => a + b, 0);
  let left = 0;
  for (let i = 0; i < nums.length; i++) {
    if (left === total - left - nums[i]) return i;
    left += nums[i];
  }
  return -1;
}
```

```python
def pivot_index(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        if left == total - left - x:
            return i
        left += x
    return -1
```

## 3. Subarray Sum Equals K (LeetCode 560)

**🟠 Medium.** Return the number of contiguous subarrays whose sum equals `k`. Values may be negative.

```text
nums = [1,1,1], k = 2 → 2
```

**Approach.** Running prefix sum + a map counting how often each prefix has occurred. At each position, add the count of `running − k`.

**Complexity.** O(n) time, O(n) space.

```typescript
function subarraySum(nums: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]);
  let running = 0, count = 0;
  for (const x of nums) {
    running += x;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}
```

```python
def subarray_sum(nums, k):
    seen = {0: 1}
    running = count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count
```

## 4. Contiguous Array (LeetCode 525)

**🟠 Medium.** In a binary array, return the length of the longest contiguous subarray with an equal number of 0s and 1s.

```text
nums = [0,1,0] → 2
```

**Approach.** Treat 0 as −1; then 'equal counts' means 'sum 0'. Store the **first** index where each prefix sum appears (with sum 0 at index −1). When a prefix repeats, the subarray between the two occurrences sums to 0.

**Complexity.** O(n) time, O(n) space.

```typescript
function findMaxLength(nums: number[]): number {
  const first = new Map<number, number>([[0, -1]]);
  let running = 0, best = 0;
  for (let i = 0; i < nums.length; i++) {
    running += nums[i] === 1 ? 1 : -1;
    if (first.has(running)) best = Math.max(best, i - first.get(running)!);
    else first.set(running, i);
  }
  return best;
}
```

```python
def find_max_length(nums):
    first = {0: -1}
    running = best = 0
    for i, x in enumerate(nums):
        running += 1 if x == 1 else -1
        if running in first:
            best = max(best, i - first[running])
        else:
            first[running] = i
    return best
```

## 5. Subarray Sums Divisible by K (LeetCode 974)

**🟠 Medium.** Return the number of non-empty subarrays whose sum is divisible by `k`.

```text
nums = [4,5,0,-2,-3,1], k = 5 → 7
```

**Approach.** Two prefixes with the same remainder mod k enclose a subarray divisible by k. Count remainders (normalized to be non-negative) and add the count of the current remainder at each step.

**Complexity.** O(n) time, O(k) space.

```typescript
function subarraysDivByK(nums: number[], k: number): number {
  const counts = new Map<number, number>([[0, 1]]);
  let running = 0, total = 0;
  for (const x of nums) {
    running = (((running + x) % k) + k) % k;   // normalize negatives in JS
    total += counts.get(running) ?? 0;
    counts.set(running, (counts.get(running) ?? 0) + 1);
  }
  return total;
}
```

```python
def subarrays_div_by_k(nums, k):
    counts = {0: 1}
    running = total = 0
    for x in nums:
        running = (running + x) % k          # Python % is already non-negative
        total += counts.get(running, 0)
        counts[running] = counts.get(running, 0) + 1
    return total
```

## 6. Range Sum Query 2D – Immutable (LeetCode 304)

**🟠 Medium.** Design `NumMatrix(matrix)` with `sumRegion(r1, c1, r2, c2)` returning the sum of the sub-rectangle, in O(1) per query.

```text
sumRegion(2,1,4,3) → 8 · sumRegion(1,1,2,2) → 11
```

**Approach.** Build a (R+1)×(C+1) prefix table with inclusion–exclusion, then answer each query with four lookups.

**Complexity.** O(R·C) build, O(1) per query.

```typescript
class NumMatrix {
  private P: number[][];
  constructor(matrix: number[][]) {
    const R = matrix.length, C = matrix[0].length;
    this.P = Array.from({ length: R + 1 }, () => new Array(C + 1).fill(0));
    for (let r = 0; r < R; r++)
      for (let c = 0; c < C; c++)
        this.P[r + 1][c + 1] = matrix[r][c] + this.P[r][c + 1] + this.P[r + 1][c] - this.P[r][c];
  }
  sumRegion(r1: number, c1: number, r2: number, c2: number): number {
    const P = this.P;
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
  }
}
```

```python
class NumMatrix:
    def __init__(self, matrix):
        R, C = len(matrix), len(matrix[0])
        self.P = [[0] * (C + 1) for _ in range(R + 1)]
        for r in range(R):
            for c in range(C):
                self.P[r + 1][c + 1] = matrix[r][c] + self.P[r][c + 1] + self.P[r + 1][c] - self.P[r][c]

    def sum_region(self, r1, c1, r2, c2):
        P = self.P
        return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]
```