Welcome to my algorithmic journey! If you’ve ever looked at a coding challenge and felt like you were staring at a brick wall, you aren’t alone. Most of the time, the secret isn’t about being a math genius, it’s about recognising the pattern.
In this series, we are breaking down the most essential coding patterns from beginner to expert level, keeping things simple, practical, and (hopefully) a little bit fun.
Today, we are diving deep into Prefix Sum.
Whether you are preparing for a big interview or just trying to write cleaner, faster code, mastering this pattern is a total game-changer.
Let’s strip away the jargon and see how it actually works!
What is Prefix Sum?
Imagine you are standing at the start of a long road, and every mile there is a sign telling you how many coins are buried under the ground at that specific spot. If I asked you, “How many coins are there between mile 3 and mile 8?”, you would normally have to walk from 3 to 8 and add them up one by one.
That works for a short walk, but what if the road is 10,000 miles long and I ask you 1,000 different questions? You’d be exhausted!
Prefix Sum is a preprocessing technique used to create a “running total” of an array. By doing a little bit of work upfront to sum up the elements as you go, you can answer any “range sum” query, asking for the total between any two points in constant time. It turns a repetitive addition task into a simple subtraction task.
The Mathematical Logic
The math behind a Prefix Sum is beautifully simple. We create a new array, let’s call it newArray, where each element at index i stores the sum of all elements from the start of the original array prevArray up to that index.
The Formula:
newArray[i] = prevArray[0] + prevArray[1] + ... + prevArray[i]
Or, more efficiently:
newArray[i] = newArray[i-1] + prevArray[i]
A Simple Example:
Let’s say we have an array of numbers: A = [3, 1, 4, 1, 5]
To build the Prefix Sum array (P), we add as we go:
- Index 0: 3
- Index 1: 3 + 1 = 4
- Index 2: 4 + 4 = 8
- Index 3: 8 + 1 = 9
- Index 4: 9 + 5 = 14
Prefix Sum Array (P): [3, 4, 8, 9, 14]
Now, if you want the sum of elements from index 2 to 4 (which are 4, 1, 5), instead of adding them, you just take the total at index 4 and subtract the total before index 2:
Result: 14–4 = 10
This works because:
P[4] = A0 + A1 + A2 + A3 + A4
P[2 — 1] = A0 + A1
So,
P[4] — P[2 — 1]= A2 + A3 + A4
Efficiency and Complexity
Before we break down the performance of this algorithm, it’s important to understand how we measure “speed” and “memory” in the coding world. We use something called Big-O Notation. If you aren’t familiar with terms like O(n) or O(1), or if you just need a quick refresher so you don’t get lost in the numbers, check out my previous guide here.
How it solves Time Complexity
Without Prefix Sum, if you want to find the sum of a range in an array of size N, you have to loop through it, which takes O(N) time. If you have M queries, your total time is O(M x N). That’s slow! With Prefix Sum, we spend O(N) time once to build the sum array. After that, every single query is answered instantly in O(1) (constant time) because it’s just a simple subtraction.
How it solves Space Complexity
The trade-off for all that speed is memory. We usually create a new array of the same size as the original to store our running totals. Therefore, Space Complexity: O(N) However, in some cases, if you don’t need to keep the original numbers, you can overwrite the original array to achieve O(1) extra space!
Where is it used? (Applications)
Financial & Sales Analytics: Imagine a dashboard showing total revenue over any custom date range. The system can now calculate the total for a week, month, or quarter instantly, regardless of how many years of data you have.
Image Processing: In computer vision (like the filters on your phone), a 2D version of Prefix Sum called a Summed-Area Table is used to quickly blur images or detect features. It allows the computer to calculate the average color of any rectangular group of pixels in constant time.
Web Analytics: Tracking cumulative website visitors or “active users” over time series data.
Database Query Optimization: Databases use it to speed up “range scans” or “aggregate queries.” When you run a query asking for data between two timestamps, the database might use prefix-style pre-computations to give you the answer faster.
Game Development: Calculating cumulative scores, resources gained over a level, or even managing lighting and shadows in 2D space.
Classic Interview Problems
If you are heading into a coding interview, there are a few “Famous” problems that almost always use Prefix Sum. Recognizing these early will save you a ton of time and stress!
You are given an array and asked to find the sum of elements between two indices multiple times. This is the “Hello World” of Prefix Sum.
You need to find an index where the sum of numbers to the left equals the sum of numbers to the right.
Subarray Sum Equals K: A classic “Level Up” problem. It combines Prefix Sum with a HashMap to find the number of subarrays that add up to a specific value K.
A very beginner-friendly problem where you track net gain/loss at each step essentially building a Prefix Sum array as you “climb.”
Implementation
Now, let’s see this pattern in action!
For these demonstrations, I’ll be using C#. However, don’t let the language choice stop you if you usually code in Python, Java, JavaScript etc. The logic and the underlying pattern remain exactly the same across all languages, only the syntax changes. Feel free to follow along and implement the logic in your own preferred language.
using System;
public class PrefixSumExample
{
public static void Main()
{
int[] nums = { 3, 1, 4, 1, 5 };
// Preprocessing: Build the Prefix Sum Array
int[] prefixSum = BuildPrefixSum(nums);
// Querying: Get sum of range [index 1 to 3] (values: 1, 4, 1)
// Expected: 6
int result = GetRangeSum(prefixSum, 1, 3);
Console.WriteLine("\nSum of range [1 to 3]: " + result);
}
public static int[] BuildPrefixSum(int[] A)
{
int n = A.Length;
int[] P = new int[n];
// The first element is always the same
P[0] = A[0];
for (int i = 1; i < n; i++)
{
// Current Total = Previous Total + Current Element
P[i] = P[i - 1] + A[i];
}
return P;
}
public static int GetRangeSum(int[] P, int left, int right)
{
// Sum(left, right) = P[right] - P[left - 1]
if (left == 0) return P[right];
return P[right] - P[left - 1];
}
}
Practice Roadmap
Theory is great, but coding is a sport. You only get better by practicing! To help you master this pattern, I’ve curated a list of LeetCode problems. To get the most out of your study time, I recommend following the 3:6:1 ratio (or the 3:5:2 if you’re feeling brave!):
30% Easy to build your confidence and grasp the core logic.
https://leetcode.com/problems/running-sum-of-1d-array/
https://leetcode.com/problems/find-pivot-index/description/
https://leetcode.com/problems/find-the-highest-altitude/
50% Medium to learn how to apply the pattern in tricky scenarios.
https://leetcode.com/problems/subarray-sum-equals-k/description/
https://leetcode.com/problems/product-of-array-except-self/description/
https://leetcode.com/problems/range-sum-query-2d-immutable/
https://leetcode.com/problems/minimum-size-subarray-sum/
https://leetcode.com/problems/contiguous-array/
20% Hard to challenge your limits and see the pattern at its peak.
https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
https://leetcode.com/problems/trapping-rain-water/description/
Don’t get discouraged if you get stuck! The goal isn’t to solve it in five minutes; the goal is to recognise the pattern. Happy coding!
Stay updated with the latest insights and tutorials by following me on Medium, dev.io and LinkedIn. For any inquiries for games or questions, feel free to reach out to me via email. I’m here to assist you with any queries you may have!
Don’t miss out on future articles and development tips!
Top comments (0)