Stage 1 · Code
Arrays & Strings
Prefix Sum
Precomputing prefix sums for O(1) range queries.
6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Prefix Sum Concept
A prefix sum array stores cumulative sums: prefix[i] = sum(arr[0..i-1]). This enables O(1) range sum queries: sum(arr[l..r]) = prefix[r+1] - prefix[l].
Go1d-prefix-sum.go
23 linesLn 1, Col 1Go
Prefix array has n+1 elements with prefix[0]=0. Range sum is difference of two prefix values.
1D Prefix Sum Patterns
- Subarray sum equals K: Count subarrays with sum K using hashmap of prefix sums.
- Maximum subarray sum: Kadane's algorithm (special case).
- Equilibrium index: Where left sum equals right sum.
- Subarrays divisible by K: Use modulo of prefix sums.
Gosubarray-sum-equals-k.go
16 linesLn 1, Col 1Go
If current prefixSum - k exists in map, subarray between them sums to k. Track frequency of prefix sums.
2D Prefix Sum
For matrix range sum queries: prefix[i+1][j+1] = matrix[i][j] + prefix[i][j+1] + prefix[i+1][j] - prefix[i][j]. Query rectangle sum in O(1).
Go2d-prefix-sum-matrix.go
20 linesLn 1, Col 1Go
Inclusion-exclusion principle for 2D. Standard pattern for matrix region sum queries.
Applications
- Range sum queries (immutable arrays)
- Subarray sum problems (equals K, divisible by K, maximum average)
- Matrix region sums (image processing, integral images)
- Difference array for range updates + prefix sum for queries
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.