Preview — Pro guide
You are seeing a portion of this guide. Sign in and upgrade to unlock the full article, quizzes, and interview answers.
Prefix Sums & Hashing: Subarray Problems in O(n)
Two of the most frequently tested DSA patterns: prefix sums convert subarray queries from O(n) to O(1), and hash maps eliminate the inner loop in most two-pass problems. Covers subarray sum equals K, two-sum variants, longest subarray with constraint, and the combined prefix-sum + hash technique.
The Pattern: Turning O(n²) into O(n)
Most array problems that seem to require nested loops — "find a subarray that does X" or "find two elements that do Y" — have an O(n) solution using one or both of these techniques:
- Prefix sums precompute cumulative sums so any subarray sum
[i..j]is answered in O(1):prefix[j+1] - prefix[i]. - Hash maps store previously seen values (or their complements) so each element can be matched in O(1) instead of O(n) inner scan.
The signal words: "subarray sum equals k", "longest subarray with sum ≤ k", "find two numbers that sum to target", "count subarrays with property". When you see these, reach for prefix sums and/or hashing before considering O(n²).