➕ Prefix Sum — JavaScript
Index: Prefix Sum Index | Parent: JS Array Index
Core Concept
Build a prefix array where prefix[i] = sum of all elements from index 0 to i-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;
}
// Range sum [L, R] inclusive:
// sum = prefix[R + 1] - prefix[L]Example:
arr: [3, 1, 2, 5, 4]
idx: 0 1 2 3 4
prefix: [0, 3, 4, 6, 11, 15]
idx: 0 1 2 3 4 5
Sum [1..3] = prefix[4] - prefix[1] = 11 - 3 = 8 ✓ (1+2+5=8)Q1. Range Sum Query — Class-Based [E]
🧠 How to Approach This
Step 1 — Recognize the pattern:
Multiple range sum queries on the same array = Pre-compute a prefix sum array once, answer each query in O(1).
Step 2 — Brute force:
Sum elements from left to right for each query → O(n) per query. With 10,000 queries that's O(n×q).
Step 3 — Optimal insight:
prefix[i] = sum of all elements from index 0 to i-1. Sum of range [L..R] = prefix[R+1] - prefix[L]. Pre-build once in O(n), query in O(1).
Step 4 — Algorithm:
1. prefix[0] = 0; prefix[i+1] = prefix[i] + nums[i]
2. sumRange(L, R) = prefix[R+1] - prefix[L]
Step 5 — Edge cases:
- L=0: prefix[0]=0, so prefix[R+1] - 0 = prefix[R+1] ✓
Way of Thinking: Build prefix once in constructor. Each query is O(1).
class NumArray {
constructor(nums) {
this.prefix = new Array(nums.length + 1).fill(0);
for (let i = 0; i < nums.length; i++) {
this.prefix[i + 1] = this.prefix[i] + nums[i];
}
}
sumRange(left, right) {
return this.prefix[right + 1] - this.prefix[left];
}
}
const obj = new NumArray([-2, 0, 3, -5, 2, -1]);
console.log(obj.sumRange(0, 2)); // 1 (-2+0+3)
console.log(obj.sumRange(2, 5)); // -1 (3-5+2-1)Q2. Subarray Sum Equals K [M][FB]
🧠 How to Approach This
Step 1 — Recognize the pattern:
Count subarrays with exact sum = prefix sum + hashmap complement trick.
Step 2 — Brute force:
All O(n²) subarrays, compute sum → O(n³) or O(n²). Need O(n).
Step 3 — Key insight:
Sum of subarray [j..i] = prefixSum[i] - prefixSum[j-1]. If this equals k, then prefixSum[j-1] = prefixSum[i] - k. So for each i, check if (currentSum - k) was seen before in the map.
Step 4 — Algorithm:
1. map = {0: 1} (prefix sum 0 seen once before we start)
2. For each num: sum += num
3. count += map.get(sum - k) ?? 0
4. map.set(sum, (map.get(sum) ?? 0) + 1)
Step 5 — Edge cases:
- k=0: counts subarrays that cancel out to zero (negative + positive)
- Negative numbers are handled naturally
Way of Thinking: Use a Map to count prefix sum occurrences. If prefixSum - k exists in the map, we found a valid subarray.
function subarraySum(nums, k) {
const map = new Map([[0, 1]]); // prefix 0 seen once
let sum = 0, count = 0;
for (const num of nums) {
sum += num;
if (map.has(sum - k)) count += map.get(sum - k);
map.set(sum, (map.get(sum) || 0) + 1);
}
return count;
}
console.log(subarraySum([1,1,1], 2)); // 2
console.log(subarraySum([1,2,3], 3)); // 2 ([1,2] and [3])Q3. Equilibrium Index [M]
🧠 How to Approach This
Step 1 — Recognize the pattern:
Find index where left sum equals right sum = running prefix sum, no extra array needed.
Step 2 — Brute force:
For each i, sum left and sum right → O(n²). Need O(n).
Step 3 — Key insight:
rightSum = total - leftSum - arr[i]. Track leftSum as you walk. At each i: if leftSum === total - leftSum - arr[i] then i is equilibrium.
Step 4 — Algorithm:
1. total = sum of all elements
2. leftSum = 0
3. For each i: if leftSum === total - leftSum - arr[i]: return i; leftSum += arr[i]
Step 5 — Edge cases:
- Single element: always equilibrium (both sides are 0)
- No equilibrium: return -1
Way of Thinking: At equilibrium index i: leftSum = totalSum - leftSum - arr[i]. No need for prefix array — track running sum.
function equilibriumIndex(arr) {
const total = arr.reduce((a, b) => a + b, 0);
let leftSum = 0;
for (let i = 0; i < arr.length; i++) {
if (leftSum === total - leftSum - arr[i]) return i;
leftSum += arr[i];
}
return -1;
}
console.log(equilibriumIndex([1, 3, 5, 2, 2])); // 2 (sum left=4, sum right=4)Q4. Product of Array Except Self [M][FB]
🧠 How to Approach This
Step 1 — Recognize the pattern:
Product of everything except self, no division, O(n) = Two-pass prefix/suffix product.
Step 2 — Brute force:
For each i, multiply all other elements → O(n²). Or total product / arr[i] but fails on zeros.
Step 3 — Key insight:
result[i] = (product of everything to the LEFT of i) × (product of everything to the RIGHT of i). Left products in one forward pass, right products in one backward pass — no extra array needed for the second pass.
Step 4 — Algorithm:
1. Forward pass: result[i] = product of all nums[0..i-1] (start with left=1)
2. Backward pass: multiply result[i] by right product (start with right=1)
Step 5 — Edge cases:
- Array with one zero: all products are 0 except at the zero index
- Array with two zeros: all products are 0
Way of Thinking: Two passes: left pass builds prefix products, right pass builds suffix products. Multiply both. No division needed.
function productExceptSelf(nums) {
const n = nums.length;
const result = new Array(n).fill(1);
// Left pass: result[i] = product of all elements left of i
let left = 1;
for (let i = 0; i < n; i++) {
result[i] = left;
left *= nums[i];
}
// Right pass: multiply by product of all elements right of i
let right = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}
return result;
}
console.log(productExceptSelf([1,2,3,4])); // [24,12,8,6]Q5. Maximum Subarray Sum — Kadane's Algorithm [M][FB]
🧠 How to Approach This
Step 1 — Recognize the pattern:
Maximum sum of a contiguous subarray = Kadane's Algorithm (dynamic programming in O(n)).
Step 2 — Brute force:
All subarrays, compute sum → O(n²) or O(n³). Need O(n).
Step 3 — Key decision at each step:
Should we extend the current subarray or start a new one? If currentSum + nums[i] > nums[i] alone, extend. Otherwise restart from nums[i]. Simplified: currentSum = max(nums[i], currentSum + nums[i]).
Step 4 — Algorithm:
1. currentSum = maxSum = nums[0]
2. For i from 1 to end: currentSum = max(nums[i], currentSum + nums[i])
3. maxSum = max(maxSum, currentSum)
Step 5 — Edge cases:
- All negative: return the least negative number
- Single element: that is the answer
Way of Thinking: At each position: should we extend current subarray or start fresh? Take the max of (currentElement alone) vs (currentElement + previousSum).
function maxSubArray(nums) {
let currentSum = nums[0];
let maxSum = 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(nums) {
let currentSum = nums[0], maxSum = nums[0];
let start = 0, end = 0, tempStart = 0;
for (let i = 1; i < nums.length; 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 { maxSum, subarray: nums.slice(start, end + 1) };
}
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // 6
console.log(maxSubArrayWithIndices([-2,1,-3,4,-1,2,1,-5,4]));
// { maxSum: 6, subarray: [4,-1,2,1] }Q6. 2D Prefix Sum — Matrix Range Query [M]
Way of Thinking: Build 2D prefix: prefix[r][c] = sum of rectangle from (0,0) to (r-1, c-1). Use inclusion-exclusion for queries.
class NumMatrix {
constructor(matrix) {
const rows = matrix.length, cols = matrix[0].length;
this.prefix = Array.from({length: rows+1}, () => new Array(cols+1).fill(0));
for (let r = 1; r <= rows; r++) {
for (let c = 1; c <= cols; c++) {
this.prefix[r][c] =
matrix[r-1][c-1] +
this.prefix[r-1][c] +
this.prefix[r][c-1] -
this.prefix[r-1][c-1];
}
}
}
sumRegion(r1, c1, r2, c2) {
return this.prefix[r2+1][c2+1]
- this.prefix[r1][c2+1]
- this.prefix[r2+1][c1]
+ this.prefix[r1][c1];
}
}
const nm = new NumMatrix([[3,0,1,4],[5,6,3,2],[1,2,0,1]]);
console.log(nm.sumRegion(0,0,1,1)); // 14 (3+0+5+6)