Quick Overview
Precomputing running totals turns any range sum into one subtraction: `prefix[R+1] - prefix[L]`. Queries drop from `O(N)` each to `O(1)`, paid for once by an `O(N)` build.
Suppose you need to calculate the sum of array elements from index L to R thousands of times. A loop takes O(N) per query. A Prefix Sum Array pre-computes cumulative totals in O(N) once, answering every subsequent query in O(1) instant time!
prefix[i] = prefix[i - 1] + arr[i - 1]
Sum(L..R) = prefix[R + 1] - prefix[L]
class PrefixSum {
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];
}
}
queryRange(left, right) {
// Returns sum of elements from index left to right inclusive in O(1)
return this.prefix[right + 1] - this.prefix[left];
}
}
const tracker = new PrefixSum([3, 1, 4, 1, 5, 9, 2]);
// Prefix array: [0, 3, 4, 8, 9, 14, 23, 25]
console.log(tracker.queryRange(1, 4)); // Elements [1, 4, 1, 5] -> Output: 11
console.log(tracker.queryRange(0, 2)); // Elements [3, 1, 4] -> Output: 8
Find the total number of continuous subarrays whose sum equals k in O(N) time:
function subarraySum(nums, k) {
const prefixCount = new Map([[0, 1]]);
let currentSum = 0;
let totalCount = 0;
for (const num of nums) {
currentSum += num;
if (prefixCount.has(currentSum - k)) {
totalCount += prefixCount.get(currentSum - k);
}
prefixCount.set(currentSum, (prefixCount.get(currentSum) || 0) + 1);
}
return totalCount;
}
console.log(subarraySum([1, 1, 1], 2)); // Output: 2
N requires messy left === 0 special casing. Allocating size N + 1 with prefix[0] = 0 eliminates boundary edge cases cleanly!Use prefix sums for range queries and subarray sum problems. Next, let's explore Recursion and Call Stack Frames!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.