Beginner LevelData Structures & Algorithms
What is the Prefix Sum technique and when is it useful?
ā Interview Prompt: Explain Prefix Sums (cumulative sum arrays), range sum queries in O(1), and 2D prefix sums.
A Prefix Sum array prefix[i] stores the sum of elements from index 0 to i.
Construction: $O(N)$
prefix[i] = prefix[i-1] + arr[i]
Range Sum Query: $O(1)$
Sum of arr[l..r] = prefix[r] - prefix[l-1] (or prefix[r] - prefix[l] + arr[l]).
Use Cases:
ā¢
Range sum queries (subarray sum equals K).
ā¢
Finding equilibrium index.
ā¢
2D prefix sums for rectangle sums in image processing.
ā¢
Difference arrays for range updates.
Code Implementation Example
typescript
// Build prefix sum ā O(N)
function buildPrefix(arr: number[]): number[] {
const prefix = [0, ...arr]; // 1-indexed for easier range queries
for (let i = 1; i < prefix.length; i++) prefix[i] += prefix[i - 1];
return prefix;
}
// Range sum [l, r] (0-indexed) ā O(1)
function rangeSum(prefix: number[], l: number, r: number): number {
return prefix[r + 1] - prefix[l];
}
const arr = [3, 1, 4, 1, 5, 9];
const prefix = buildPrefix(arr);
console.log(rangeSum(prefix, 1, 4)); // 1+4+1+5 = 11š”Prefix sum enabling O(1) range sum queries after O(N) preprocessing.
šÆ Interview Key Takeaway
Prefix Sums preprocess an array in O(N) to answer range sum queries in O(1). Essential for problems involving subarray sums.
#DSA#Prefix Sum#Arrays#Range Queries#Beginner
Back to all Data Structures & Algorithms Questionsā