Prefix Sum
The Prefix Sum Pattern
Precompute cumulative totals once, then answer any range-sum query as the difference of two prefix values. Pairing prefix sums with a hash map turns "count subarrays summing to k" into a single pass.
Interactive problems
Free to open
How do you recognise a prefix sum problem?
The problem asks about sums or counts over many subarrays or ranges, especially with repeated queries over unchanging data. "Subarray sum equals k" and "range sum query" are the standard forms.
What is the time complexity of the prefix sum pattern?
O(n) preprocessing, then O(1) per range query — against O(n) per query when summing directly.
Prefix Sum practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Prefix Sum problems by difficulty and complexity
The difficulty, running time and extra space of every prefix sum solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Introduction to Prefix Sums | Easy | Ω(N + Q) | Θ(N + Q) | O(N + Q) | O(N) |
| Count Vowels in Ranges | Medium | Ω(N + Q) | Θ(N + Q) | O(N + Q) | O(N + Q) |
| Product of Array Except Self | Medium | Ω(n) | Θ(n) | O(n) | O(1) |
| Subarray Sum Equals K | Medium | Ω(N) | Θ(N) | O(N) | O(N) |
Related patterns and concepts
The underlying technique is covered from first principles in the prefix sum lesson in the DSA visualizer curriculum. Prefix Sum is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree