← All Comparisons
Kadane's Algorithm vs Prefix Sum
Quick Answer
Use Kadane's Algorithm when you need the maximum sum of any contiguous subarray in a single pass. Use Prefix Sum when you need range sum queries, subarray sum equals K, or any problem where you repeatedly ask "what is the sum from index i to j?"
Side-by-Side Comparison
| Aspect | Kadane's Algorithm | Prefix Sum |
|---|---|---|
| Primary use | Maximum sum of contiguous subarray | Range sum queries, subarray sum equals K |
| Preprocessing | None (single pass) | O(n) to build prefix array |
| Query time | N/A (one-shot answer) | O(1) per range query |
| Time complexity | O(n) | O(n) build + O(1) per query |
| Space complexity | O(1) | O(n) for prefix array |
| Key insight | Either extend current subarray or start fresh | sum(i, j) = prefix[j+1] - prefix[i] |
| Key signal | "Maximum subarray sum", "largest sum contiguous" | "Range sum", "subarray sum equals K", "multiple queries" |
When to Use Kadane's Algorithm
- -The problem asks for the maximum sum of any contiguous subarray (Maximum Subarray, Maximum Sum Circular Subarray).
- -You need a single pass solution with O(1) space.
- -The problem is about optimizing a running sum — keep it if positive, reset if it becomes negative.
When to Use Prefix Sum
- -You have multiple range sum queries (Range Sum Query, 2D prefix sums for matrix).
- -The problem asks for subarray sum equals K — use prefix sum + hash map to count prefix[j] - prefix[i] = K.
- -You need to answer many queries over different ranges; preprocessing pays off.
- -The problem involves 2D arrays and rectangular region sums (Range Sum Query 2D).
Decision Framework
- Does the problem ask for "maximum subarray sum" or "largest sum contiguous"? Use Kadane's.
- Do you need to answer many "sum from i to j" queries? Use Prefix Sum.
- Does the problem ask for "number of subarrays with sum K"? Use Prefix Sum + Hash Map.
- Is it a 2D matrix with rectangular region sums? Use 2D Prefix Sum.
- Do you need O(1) space and a single pass? Kadane's fits; Prefix Sum needs O(n) space.
Example Problems
Kadane's Algorithm
- 1.Maximum Subarray — Classic Kadane's: track current sum and max sum, reset when current goes negative.
- 2.Maximum Sum Circular Subarray — Kadane's for non-circular max; also check total - min subarray for wrap-around case.
- 3.Best Time to Buy and Sell Stock — Variant: max profit = max subarray sum of daily price differences.
Prefix Sum
- 1.Range Sum Query — Build prefix array once; each query is prefix[right+1] - prefix[left] in O(1).
- 2.Subarray Sum Equals K — Prefix sum + hash map: count how many prefix[j] - prefix[i] = K.
- 3.Range Sum Query 2D — 2D prefix sums for O(1) rectangular region sum queries.