➕ Prefix Sum Technique — Complete Guide

Index: Prefix Sum Index | Parent: Array Index

---

What is Prefix Sum?

Precompute cumulative sums so any range query can be answered in O(1) instead of O(n).

Original:  [3, 1, 4, 1, 5, 9, 2, 6]
Prefix:    [0, 3, 4, 8, 9,14,23,25,31]
            ↑ always start with 0

Sum from index 2 to 5 (values 4,1,5,9):
= prefix[6] - prefix[2]
= 23 - 4
= 19 ✅

Formula

prefix[i] = prefix[i-1] + arr[i-1]
rangeSum(L, R) = prefix[R+1] - prefix[L]

When to Use Prefix Sum?

• Range sum queries (sum of subarray from L to R)
• Multiple queries on same array
• Find subarray with specific sum
• Keywords: "range sum", "subarray sum", "between index i and j"

---

Build Prefix Sum Array

function buildPrefix(array $arr): array {
    $n = count($arr);
    $prefix = array_fill(0, $n + 1, 0);

    for ($i = 0; $i < $n; $i++) {
        $prefix[$i + 1] = $prefix[$i] + $arr[$i];
    }

    return $prefix;
}

// Range sum query O(1)
function rangeSum(array $prefix, int $L, int $R): int {
    return $prefix[$R + 1] - $prefix[$L];
}

$arr    = [3, 1, 4, 1, 5, 9, 2, 6];
$prefix = buildPrefix($arr);

echo rangeSum($prefix, 2, 5); // 19 (4+1+5+9)
echo rangeSum($prefix, 0, 3); // 9  (3+1+4+1)

function buildPrefix(arr) {
    const prefix = new Array(arr.length + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

function rangeSum(prefix, L, R) {
    return prefix[R + 1] - prefix[L];
}

---

Interview Questions — Prefix Sum

---

Q1. Range Sum Query [E][FB]

Question: Given array, answer multiple range sum queries efficiently.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Multiple queries on same array = pre-compute prefix sums once, answer each query in O(1).

Step 2 — Brute force:

Sum elements from L to R for each query → O(n) per query. If you have m queries: O(n×m). Prefix sum gives O(n + m).

Step 3 — Insight:

prefix[i] = sum of first i elements. Sum from L to R = prefix[R+1] - prefix[L].

Step 4 — Algorithm:

1. Build: prefix[0]=0; prefix[i+1] = prefix[i] + arr[i]

2. Query: return prefix[R+1] - prefix[L]

Step 5 — Edge cases:

- 0-indexed vs 1-indexed: be careful about off-by-one

- Single element query (L=R): prefix[R+1] - prefix[R] = arr[R] ✓

class NumArray { private array $prefix;

public function __construct(array $nums) { $n = count($nums); $this->prefix = array_fill(0, $n + 1, 0); for ($i = 0; $i < $n; $i++) { $this->prefix[$i + 1] = $this->prefix[$i] + $nums[$i]; } }

public function sumRange(int $left, int $right): int { return $this->prefix[$right + 1] - $this->prefix[$left]; } }

$obj = new NumArray([-2, 0, 3, -5, 2, -1]); echo $obj->sumRange(0, 2); // 1 (-2+0+3) echo $obj->sumRange(2, 5); // -1 (3-5+2-1) echo $obj->sumRange(0, 5); // -3

---

### Q2. Subarray Sum Equals K `[M][FB]`

**Question:** Count subarrays in `[1,2,3]` that sum to k=3.

---

> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> Count subarrays with exact sum = Prefix sum + hash map (the "complement" trick).
>
> **Step 2 — Brute force:**
> Check every (start, end) pair: O(n²). Need O(n).
>
> **Step 3 — Key insight:**
> If prefix sum at index j is P, and we want a subarray summing to k, we need some earlier prefix P-k. A hash map counts how many times we've seen P-k before reaching j.
>
> ```
> sum[i..j] = prefix[j] - prefix[i-1] = k
> → prefix[i-1] = prefix[j] - k
> ```
>
> **Step 4 — Algorithm:**
> 1. Initialize seen={0:1} (empty prefix sum seen once)
> 2. For each element: prefixSum += num
> 3. count += seen.get(prefixSum - k, 0)
> 4. seen[prefixSum]++
>
> **Step 5 — Edge cases:**
> - k can be 0 (subarrays summing to 0) or negative
> - Initialize seen[0]=1 handles subarrays starting at index 0
> - Must count BEFORE updating seen (or you'd count the element as its own subarray)

arr=[1,1,1] k=2 prefix: [0,1,2,3]

At j=1: prefix=2, need prefix-k=0 → seen[0]=1 → count+=1 At j=2: prefix=3, need prefix-k=1 → seen[1]=1 → count+=1 Answer: 2 (subarrays [1,1] starting at 0 and 1)

function subarraySum(array $nums, int $k): int { $count = 0; $prefixSum = 0; $seen = [0 => 1]; // prefix 0 seen once (empty subarray)

foreach ($nums as $num) { $prefixSum += $num; $needed = $prefixSum - $k;

if (isset($seen[$needed])) { $count += $seen[$needed]; }

$seen[$prefixSum] = ($seen[$prefixSum] ?? 0) + 1; }

return $count; }

echo subarraySum([1, 1, 1], 2); // 2 echo subarraySum([3, 4, 7, 2, -3, 1, 4, 2], 7); // 4

function subarraySum(nums, k) { let count = 0, prefixSum = 0; const seen = new Map([[0, 1]]); for (const num of nums) { prefixSum += num; count += seen.get(prefixSum - k) ?? 0; seen.set(prefixSum, (seen.get(prefixSum) ?? 0) + 1); } return count; }

**Time:** O(n) | **Space:** O(n)

---

### Q3. Equilibrium Index `[M]`

**Question:** Find index where left sum equals right sum.

---

> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> Balance point problem — compare left portion vs right portion at each index.
>
> **Step 2 — Key insight:**
> Total sum = leftSum + arr[i] + rightSum. If leftSum == rightSum, then leftSum = (total - arr[i]) / 2. But easier: track leftSum as you go; compute rightSum = total - leftSum - arr[i].
>
> **Step 3 — Algorithm:**
> 1. total = sum of all elements
> 2. leftSum = 0
> 3. For each index i: rightSum = total - leftSum - arr[i]
> 4. If leftSum == rightSum → return i
> 5. leftSum += arr[i]
>
> **Step 4 — Edge cases:**
> - Multiple equilibrium points: return first found
> - All zeros: every index is an equilibrium
> - Empty after edges: like [-1, 2, -1] → index 1

[1, 7, 3, 6, 5, 6] ↑ Left = 1+7+3 = 11 Right = 5+6 = 11 ✅ index 3

function findEquilibrium(array $arr): int { $totalSum = array_sum($arr); $leftSum = 0;

foreach ($arr as $i => $val) { // Right sum = total - leftSum - arr[i] $rightSum = $totalSum - $leftSum - $val;

if ($leftSum === $rightSum) return $i;

$leftSum += $val; }

return -1; // not found }

echo findEquilibrium([1, 7, 3, 6, 5, 6]); // 3

---

### Q4. Product Array Except Self `[M][FB]`

**Question:** Return array where `output[i]` = product of all elements except `arr[i]`. No division.

---

> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> "Product except self" = left product prefix × right product suffix.
>
> **Step 2 — Why no division:**
> Division fails with zeros. The left×right pass avoids division entirely.
>
> **Step 3 — Key insight:**
> result[i] = (product of all elements before i) × (product of all elements after i).
> Compute these two in two separate passes.
>
> **Step 4 — Algorithm:**
> 1. Left pass: result[i] = product of arr[0..i-1]. Start with result[0]=1 (nothing to left).
> 2. Right pass (reverse): multiply result[i] by running rightProduct. Start rightProduct=1.
>
> **Step 5 — Edge cases:**
> - One zero: only position at zero gets non-zero product
> - Two or more zeros: all products are 0

arr: [1, 2, 3, 4] Left: [1, 1, 2, 6] (left[i] = product of arr[0..i-1]) Right: [24,12, 4, 1] (right[i] = product of arr[i+1..n-1]) Output: [24,12, 8, 6] (left[i] * right[i])

function productExceptSelf(array $nums): array { $n = count($nums); $result = array_fill(0, $n, 1);

// Left pass: result[i] = product of all elements to the LEFT $leftProduct = 1; for ($i = 0; $i < $n; $i++) { $result[$i] = $leftProduct; $leftProduct *= $nums[$i]; }

// Right pass: multiply by product of all elements to the RIGHT $rightProduct = 1; for ($i = $n - 1; $i >= 0; $i--) { $result[$i] = $rightProduct; $rightProduct = $nums[$i]; }

return $result; }

print_r(productExceptSelf([1, 2, 3, 4])); // [24,12,8,6]

**Time:** O(n) | **Space:** O(1) (not counting output)

---

### Q5. Maximum Subarray Sum (Kadane's Algorithm) `[M][FB]`

**Question:** Find contiguous subarray with maximum sum.

---

> **🧠 How to Approach This**
>
> **Step 1 — Recognize the pattern:**
> Maximum subarray sum = Kadane's Algorithm (a greedy approach using running sum).
>
> **Step 2 — Brute force:**
> Check every subarray: O(n²). Need O(n).
>
> **Step 3 — Kadane's insight:**
> At each position, decide: should I extend the existing subarray or start fresh here?
> - If currentSum + arr[i] > arr[i]: extend (the previous contribution is positive)
> - If arr[i] > currentSum + arr[i]: start fresh at arr[i] (previous contribution was dragging us down)
>
> This simplifies to: `currentSum = max(arr[i], currentSum + arr[i])`
>
> **Step 4 — Algorithm:**
> 1. currentSum = nums[0], maxSum = nums[0]
> 2. For i from 1 to n-1: currentSum = max(nums[i], currentSum + nums[i])
> 3. maxSum = max(maxSum, currentSum)
>
> **Step 5 — Edge cases:**
> - All negative: return the least negative element (max of all elements)
> - Single element: return it
> - All positive: return sum of entire array

[-2, 1, -3, 4, -1, 2, 1, -5, 4] start fresh ↑ extend: 4,-1,2,1 = 6 ← max

function maxSubarraySum(array $nums): int { $maxSum = $nums[0]; $currentSum = $nums[0];

for ($i = 1; $i < count($nums); $i++) { // Either extend current subarray or start new one here $currentSum = max($nums[$i], $currentSum + $nums[$i]); $maxSum = max($maxSum, $currentSum); }

return $maxSum; }

echo maxSubarraySum([-2,1,-3,4,-1,2,1,-5,4]); // 6 ([4,-1,2,1])

function maxSubarraySum(nums) { let maxSum = nums[0], currentSum = nums[0]; for (let i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; }

**Extension — return the subarray itself:**

function maxSubarrayWithIndices(array $nums): array { $maxSum = $nums[0]; $currentSum = $nums[0]; $start = $end = $tempStart = 0;

for ($i = 1; $i < count($nums); $i++) { if ($nums[$i] > $currentSum + $nums[$i]) { $currentSum = $nums[$i]; $tempStart = $i; } else { $currentSum += $nums[$i]; }

if ($currentSum > $maxSum) { $maxSum = $currentSum; $start = $tempStart; $end = $i; } }

return [ 'sum' => $maxSum, 'subarray' => array_slice($nums, $start, $end - $start + 1), ]; }

---

### Q6. 2D Prefix Sum (Matrix Range Query) `[M]`

function build2DPrefix(array $matrix): array { $m = count($matrix); $n = count($matrix[0]); $prefix = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

for ($i = 1; $i <= $m; $i++) { for ($j = 1; $j <= $n; $j++) { $prefix[$i][$j] = $matrix[$i-1][$j-1] + $prefix[$i-1][$j] + $prefix[$i][$j-1]

• $prefix[$i-1][$j-1];

} } return $prefix; }

// Sum of submatrix from (r1,c1) to (r2,c2) function matrixRangeSum(array $prefix, int $r1, int $c1, int $r2, int $c2): int { return $prefix[$r2+1][$c2+1]

• $prefix[$r1][$c2+1]
• $prefix[$r2+1][$c1]

+ $prefix[$r1][$c1]; }

---

## Prefix Sum Summary

| Problem | Technique | Time |
|---------|-----------|------|
| Range sum query | Build prefix array | O(n) build, O(1) query |
| Subarray sum = k | Prefix + hash map | O(n) |
| Equilibrium index | Running left + total | O(n) |
| Product except self | Left/right product pass | O(n) |
| Max subarray sum | Kadane's (running max) | O(n) |
| 2D range query | 2D prefix sum | O(mn) build, O(1) query |