Arrays & Strings
Foundation of DSA — master traversal, manipulation, and subarray techniques
0/52 solved
Prefix Sum
Precompute cumulative sums for O(1) range queries
Approach
Build a prefix sum array where prefix[i] = sum of elements from index 0 to i-1. To get sum of subarray [l, r], compute prefix[r+1] - prefix[l]. For 'subarray sum equals K' problems, use a HashMap storing prefix sum frequencies.
How to Recognize
Problem asks for sum/count in a subarray or range — prefix sum precomputes this
Keywords: 'subarray sum equals K', 'range sum query', 'contiguous array'
Brute force involves nested loops summing subarrays (O(n²)) — prefix sum reduces to O(n)
Problem involves cumulative frequency, running totals, or prefix-based calculations
If you see 'number of subarrays with sum = target', think prefix sum + HashMap
2D range sum queries — apply prefix sum in both dimensions with inclusion-exclusion
Product of array except self — prefix and suffix products are a variant
Pro Tips
Use a HashMap to store prefix sum frequencies for O(1) lookup when target sum is involved
For 2D prefix sums, apply inclusion-exclusion: sum(r1,c1,r2,c2) = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1]
Watch for integer overflow — use long when summing large arrays
Always initialize HashMap with (0, 1) — the empty prefix has sum 0 with count 1
Contiguous Array (equal 0s and 1s): treat 0 as -1, then find longest subarray with sum 0 using prefix sum
For 'divisible by K': use modular arithmetic on prefix sums; handle negative remainders carefully
10
Total
3
Easy
5
Medium
2
Hard
Time
O(n)
Space
O(n)