O(1) range queries and subarray sum lookups using cumulative totals
Precompute cumulative values so any range sum sum(nums[i..j]) is computed in O(1) time as prefix[j+1] - prefix[i], or combined with a Hash Map to find subarrays in O(N).
Core Invariant: Sum(i..j) = Prefix[j] - Prefix[i-1] = target implies Prefix[i-1] = Prefix[j] - target. By storing seen prefix sums in a Hash Map, we can count or find valid starting indices in O(1)!
Frequent updates/modifications to array elements (use Fenwick Tree / Segment Tree for O(log n) dynamic updates).
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
prefix_counts = {0: 1} # Base case: sum 0 occurs once before array starts
curr_sum = 0
total_subarrays = 0
for num in nums:
curr_sum += num
# If (curr_sum - k) was seen before, those prior points form valid subarrays
diff = curr_sum - k
if diff in prefix_counts:
total_subarrays += prefix_counts[diff]
prefix_counts[curr_sum] = prefix_counts.get(curr_sum, 0) + 1
return total_subarrays# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #253 | Meeting Rooms II ArrayTwo PointersGreedySortingHeap (Priority Queue)Prefix Sum | Medium | 100% | 52.7% | ||
| #560 | Subarray Sum Equals K ArrayHash TablePrefix Sum | Medium | 88% | 47.7% | ||
| #238 | Product of Array Except Self ArrayPrefix Sum | Medium | 100% | 69.1% | ||
| #528 | Random Pick with Weight ArrayMathBinary SearchPrefix SumRandomized | Medium | 100% | 49.2% | ||
| #713 | Subarray Product Less Than K ArrayBinary SearchSliding WindowPrefix Sum | Medium | 100% | 54.7% | ||
| #410 | Split Array Largest Sum ArrayBinary SearchDynamic ProgrammingGreedyPrefix Sum | Hard | 100% | 60.9% | ||
| #1004 | Max Consecutive Ones III ArrayBinary SearchSliding WindowPrefix Sum | Medium | 88% | 68.0% | ||
| #724 | Find Pivot Index ArrayPrefix Sum | Easy | 100% | 63.2% | ||
| #209 | Minimum Size Subarray Sum ArrayBinary SearchSliding WindowPrefix Sum | Medium | 88% | 52.2% | ||
| #525 | Contiguous Array ArrayHash TablePrefix Sum | Medium | 88% | 51.7% | ||
| #1423 | Maximum Points You Can Obtain from Cards ArraySliding WindowPrefix Sum | Medium | 100% | 58.0% | ||
| #1838 | Frequency of the Most Frequent Element ArrayBinary SearchGreedySliding WindowSortingPrefix Sum | Medium | 100% | 45.0% | ||
| #1094 | Car Pooling ArraySortingHeap (Priority Queue)SimulationPrefix Sum | Medium | 89% | 56.4% | ||
| #1352 | Product of the Last K Numbers ArrayMathDesignData StreamPrefix Sum | Medium | 100% | 63.0% | ||
| #1413 | Minimum Value to Get Positive Step by Step Sum ArrayPrefix Sum | Easy | 100% | 64.8% | ||
| #974 | Subarray Sums Divisible by K ArrayHash TablePrefix Sum | Medium | 72% | 56.5% | ||
| #304 | Range Sum Query 2D - Immutable ArrayDesignMatrixPrefix Sum | Medium | 71% | 58.6% | ||
| #523 | Continuous Subarray Sum ArrayHash TableMathPrefix SumPigeonhole Principle | Medium | 63% | 31.5% | ||
| #862 | Shortest Subarray with Sum at Least K ArrayBinary SearchQueueSliding WindowHeap (Priority Queue)Prefix SumMonotonic Queue | Hard | 100% | 0.3% | ||
| #2559 | Count Vowel Strings in Ranges ArrayStringPrefix Sum | Medium | 88% | 67.9% | ||
| #1664 | Ways to Make a Fair Array ArrayPrefix Sum | Medium | 100% | 67.3% | ||
| #2251 | Number of Flowers in Full Bloom ArrayHash TableBinary SearchSortingPrefix SumOrdered Set | Hard | 100% | 58.0% | ||
| #303 | Range Sum Query - Immutable ArrayDesignPrefix Sum | Easy | 63% | 72.7% | ||
| #325 | Medium | 63% | 50.9% | |||
| #1732 | Find the Highest Altitude ArrayPrefix Sum | Easy | 52% | 0.8% | ||
| #2021 | Brightest Position on Street ArraySortingPrefix SumOrdered Set | Medium | 100% | 60.7% | ||
| #2406 | Divide Intervals Into Minimum Number of Groups ArrayTwo PointersGreedySortingHeap (Priority Queue)Prefix Sum | Medium | 88% | 63.6% | ||
| #2448 | Minimum Cost to Make Array Equal ArrayBinary SearchGreedySortingPrefix Sum | Hard | 75% | 46.8% | ||
| #1590 | Make Sum Divisible by P ArrayHash TablePrefix Sum | Medium | 65% | 42.6% | ||
| #689 | Maximum Sum of 3 Non-Overlapping Subarrays ArrayDynamic ProgrammingSliding WindowPrefix Sum | Hard | 63% | 59.9% | ||
| #1524 | Number of Sub-arrays With Odd Sum ArrayMathDynamic ProgrammingPrefix Sum | Medium | 100% | 55.7% | ||
| #1674 | Minimum Moves to Make Array Complementary ArrayHash TablePrefix Sum | Medium | 100% | 0.6% | ||
| #2483 | Minimum Penalty for a Shop StringPrefix Sum | Medium | 100% | 71.2% | ||
| #2615 | Sum of Distances ArrayHash TablePrefix Sum | Medium | 100% | 50.3% | ||
| #2381 | Shifting Letters II ArrayStringPrefix Sum | Medium | 100% | 0.5% | ||
| #2145 | Count the Hidden Sequences ArrayPrefix Sum | Medium | 96% | 56.7% | ||
| #2874 | Maximum Value of an Ordered Triplet II ArrayPrefix Sum | Medium | 88% | 56.4% | ||
| #2873 | Maximum Value of an Ordered Triplet I ArrayPrefix Sum | Easy | 88% | 0.6% | ||
| #2438 | Range Product Queries of Powers ArrayBit ManipulationPrefix Sum | Medium | 68% | 61.2% | ||
| #1658 | Minimum Operations to Reduce X to Zero ArrayHash TableBinary SearchSliding WindowPrefix Sum | Medium | 54% | 0.5% | ||
| #3494 | Find the Minimum Amount of Time to Brew Potions ArraySimulationPrefix Sum | Medium | 50% | 62.7% | ||
| #1480 | Running Sum of 1d Array ArrayPrefix Sum | Easy | 50% | 87.0% | ||
| #3191 | Minimum Operations to Make Binary Array Elements Equal to One I ArrayBit ManipulationQueueSliding WindowPrefix Sum | Medium | 50% | 80.4% | ||
| #3652 | Best Time to Buy and Sell Stock using Strategy ArraySliding WindowPrefix Sum | Medium | 50% | 59.7% | ||
| #1930 | Unique Length-3 Palindromic Subsequences Hash TableStringBit ManipulationPrefix Sum | Medium | 39% | 73.8% | ||
| #1371 | Find the Longest Substring Containing Vowels in Even Counts Hash TableStringBit ManipulationPrefix Sum | Medium | 38% | 75.6% | ||
| #1769 | Minimum Number of Operations to Move All Balls to Each Box ArrayStringPrefix Sum | Medium | 38% | 90.2% | ||
| #3714 | Longest Balanced Substring II Hash TableStringPrefix Sum | Medium | 27% | 41.9% | ||
| #1878 | Get Biggest Three Rhombus Sums in a Grid ArrayMathSortingHeap (Priority Queue)MatrixPrefix Sum | Medium | 100% | 71.3% | ||
| #2439 | Minimize Maximum of Array ArrayBinary SearchDynamic ProgrammingGreedyPrefix Sum | Medium | 100% | 46.6% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
O(1) range queries and subarray sum lookups using cumulative totals It is categorized under Fundamentals and features 220 curated interview problems across Easy (18), Medium (141), and Hard (61) difficulties.
Companies frequently asking Prefix Sum & Hash Map questions include Google, Amazon, Microsoft, Meta, Bloomberg, Infosys.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.