Prefix sums and two pointers

Why it matters

Many array questions ask about a piece of the array, not the whole thing. A sales report asks for the total of the days from March 3 to March 10. A video editor asks for the average brightness of one frame region. A trading app asks for the change in price between two times. If you answer each question by adding the values again, a thousand questions over a million values means a billion additions. This lesson shows two patterns that cut that work sharply. The first is prefix sums, which pay a single pass up front to answer any range in one subtraction. The second is two pointers, which solve many pair and scan questions in one pass without a nested loop.

Both patterns appear constantly in interviews, and both are short once you see the shape. The hash table in the last section adds a third idea that solves a harder counting question. By the end of this lesson you should be able to recognise each pattern from the wording of a problem.

The idea: a bank statement with a running balance

Think about a bank statement. It lists each transaction, and beside each line it shows the running balance, the money you had after that transaction. Suppose you want to know how much money moved between line 3 and line 7. You do not add up the transactions from line 4 to line 7 one by one. You take the balance after line 7 and subtract the balance after line 3. The difference is exactly the sum of the transactions in between.

A prefix sum array is a running balance for numbers. The entry at position k holds the total of the first k values. Position 0 holds 0, because the sum of nothing is 0. Once you have these totals, the sum of any range is one subtraction, no matter how long the range is.

Building the prefix sums

Let the array be a with n values, numbered from 0. Make a new array prefix with n + 1 entries. Set prefix[0] to 0. Then for each i from 0 to n - 1, set prefix[i + 1] to prefix[i] + a[i]. Each new entry adds one value to the entry before it.

Here is the array 2, 4, 1, 7, 3 with its prefix sums:

The value at position 5 is 17, which is the total of all five values: 2 + 4 + 1 + 7 + 3. The value at position 2 is 6, which is 2 + 4. The array holds one extra entry at the front, which is the trick that makes the formula clean.

Array 2 4 1 7 3 above its prefix row 0 2 6 7 14 17, with the range from index 1 to 3 highlighted

The range formula

Suppose you want the sum of the values from index l to index r, both included, where l and r count from 0. The prefix row gives you the total up to but not including position r + 1, and the total up to but not including position l. Subtract the second from the first:

sum of a[l..r] = prefix[r + 1] - prefix[l]

Check it on the figure. The range from index 1 to index 3 holds the values 4, 1 and 7. Its sum is 12. The formula gives prefix[4] - prefix[1], which is 14 minus 2, or 12. The entry at position 1 removes the first value, the value 2 at index 0, and the entry at position 4 includes everything up to index 3. The + 1 in r + 1 is the step that most learners get wrong, so the next section shows the error on purpose.

The figure highlights the two entries used by the formula. Notice that the entries of prefix that you read are at positions 1 and 4, while the values that the answer uses are at indexes 1 to 3 of the original array. Those two sets of positions are offset by one, and keeping the offset straight is the whole skill.

A program that answers queries

The next program reads an array, builds its prefix sums, then answers a list of range questions. Each question costs one subtraction. Type the input exactly as shown.

Type this into the Input box:

6
3 1 4 1 5 9
3
1 3
0 5
4 4

The program prints:

6
23
5

Trace the three answers. The array is 3, 1, 4, 1, 5, 9, and its prefix row is 0, 3, 4, 8, 9, 14, 23. The first query asks for indexes 1 to 3, which are the values 1, 4 and 1. The formula gives prefix[4] - prefix[1], which is 9 minus 3, so 6. The second query asks for all six values, and the formula gives prefix[6] - prefix[0], which is 23 minus 0. The third query asks for the single value at index 4, which is 5. The formula gives prefix[5] - prefix[4], which is 14 minus 9.

The prefix array uses long long, not int. A sum of many large values can pass the limit of an int, which is about two billion. Using long long is the normal choice for sums, and it costs little. The vector is declared with n + 1 entries and filled with 0, so prefix[0] is already correct before the loop begins.

Why this is faster

Without prefix sums, each query adds up to n values, so q queries cost about n times q steps. With prefix sums, the work is one pass to build the row, which is O(n), plus one constant-time subtraction per query. For a million values and a million queries, that is the difference between about a trillion additions and about two million steps. Interviewers look for this comparison, so state it clearly: "one O(n) pass to build, then O(1) per query, total O(n + q)".

The space cost is one extra array of n + 1 numbers, which is O(n). The trade is a little memory for a large saving in time, and that trade is nearly always worth it when the same array is queried many times.

Two pointers: one idea, many problems

Two pointers is a pattern, not a single algorithm. You keep two indexes into an array, you move them by a rule, and each move throws away some part of the search space for good. The loop runs until the indexes meet or pass each other. Because each index moves in one direction only, the loop touches each element a bounded number of times, and the total cost is O(n) even though the logic looks like a nested search.

The most famous use is the pair sum on a sorted array. You are given a sorted array and a target. You must decide whether two different values add up to the target. A brute-force answer tries every pair, which is O(n squared). The two-pointer answer is one pass, and its key is that the array is sorted.

Put left at the smallest value and right at the largest. Look at their sum. If the sum is equal to the target, you have found the pair. If the sum is smaller than the target, you need a bigger sum, and the only way to get one is to move left to a bigger value, because right already holds the biggest value. If the sum is bigger than the target, move right to a smaller value. Each step discards one of the two values that cannot be part of a pair with the other pointer's current value, so no pair is ever missed.

Sorted array 1 2 4 6 8 9 12 15 with left at the first value and right at the last, and the pair 1 and 9 highlighted

Step through the search above. The array is sorted and the target is 10. Watch the sum, and watch which pointer moves. Each time the sum is too big, right moves down. Each time it is too small, left moves up. The search ends when the pair 1 and 9 is found.

Here is the program. It reads the target and the sorted array, then prints the first pair it finds.

Type this into the Input box:

8 10
1 2 4 6 8 9 12 15

The program prints:

found 1 + 9 = 10

Trace the search. The pointers start at 1 (index 0) and 15 (index 7). Their sum is 16, which is bigger than 10, so right moves to 12. The sum is now 13, still too big, so right moves to 9. The sum is 1 + 9 = 10, and the program stops. Only three pairs were examined, out of the twenty-eight possible pairs of eight values. That is the power of the idea.

The rule that makes this correct depends on sorting. Move left up only when the sum is too small, and it only helps if the array rises from left to right. In an unsorted array the rule can throw away the right answer. Test that yourself: change the input to 1 15 2 9 4 12 6 8, and the answer may be wrong. Two pointers is a sorted-array tool. Check the order before you reach for it.

The program stops at the first pair. If you want to count all the pairs, the change is small: when the sum equals the target, add one to a counter, then move both pointers, because the values are distinct and each pointer is used once in a pair. The practice list has that version.

Why each move is safe

It is worth proving the rule once, because an interviewer may ask you to. Suppose the sum is too small. Let right be the current big end. Any pair that uses right as its large value would need the other value to be at least target - a[right]. Because left already holds the smallest value still in play, and the sum with right is too small, the value at left cannot pair with anything at or below right. That is why left can move up. The same reasoning applies when the sum is too big, and right moves down. Each move discards only values that cannot be part of an answer.

Removing duplicates from a sorted array

A second two-pointer pattern uses two indexes that move at different speeds, both forward. The slow index marks the last place where a new value was kept. The fast index scans ahead through the array. When the fast value differs from the slow value, it is a new value, so the slow index moves forward and takes the new value. When it is the same, the fast index simply keeps scanning.

Because the array is sorted, equal values are next to each other, so one comparison with the most recent kept value is enough. The example below removes duplicates in place and prints the count and the values.

Type this into the Input box:

7
1 1 2 2 2 5 9

The program prints:

distinct = 4
1 2 5 9 

Trace it. The slow index starts at 0, which holds the first 1. The fast index walks from 1. At index 1 the value is 1, the same as the kept 1, so nothing happens. At index 2 the value is 2, which differs, so slow becomes 1 and a[1] is set to 2. The values at index 3 and 4 are 2, equal to the kept 2, so they are skipped. At index 5 the value is 5, which becomes a[2]. At index 6 the value 9 becomes a[3]. The loop ends with slow at 3, so the distinct count is slow + 1, which is 4. Only the first four positions matter; the values after them are leftovers and are ignored.

The check if (n == 0) is needed because the line a[0] would read an element that does not exist. It is a small guard, and interviewers look for it in every answer that starts from index 0.

The method runs in O(n) time and O(1) extra space, because it changes the array in place. Compare it with the set-based answer that works on an unsorted array in O(n) time and O(n) space. Stating both and explaining the trade-off is the mark of a strong answer.

Counting subarrays with a running total and a hash table

Some questions ask for counts, not for one pair. A common example is this: how many contiguous subarrays add up to exactly k? The values can be negative and zero, so the array is not sorted, and the two-pointer method does not apply. The answer comes from prefix sums combined with a hash table. A hash table, called unordered_map in C++, stores pairs of keys and values and finds any key in about constant time. You will meet it properly in the sets and maps module, so for now, think of it as a lookup book where you can ask "have I seen this number before, and how many times?"

The key idea is this. Let P be the prefix sum up to the current position. A subarray that ends here and sums to k starts right after some earlier position where the prefix sum was P - k. So for each position, count how many earlier prefix sums equal P - k, and add that count to the answer. Then record the current prefix sum in the table, so that later positions can use it.

Step through the lookups above. Each step looks up the value that would finish a matching subarray, then records the current prefix sum. The table grows as you go, and each lookup is about constant time, so the whole pass is O(n) on average.

Here is the program. It reads n, k, and the values, and prints the count.

Type this into the Input box:

6 3
1 2 3 -1 1 2

The program prints:

4

Trace it with the running prefix sums. The prefix values after each value are 1, 3, 6, 5, 6 and 8. Before the loop, the table holds one entry, prefix 0, seen once.

The four matches are the subarrays 1 2 (indexes 0 to 1), the single 3 (index 2), the run 3 -1 1 (indexes 2 to 4), and the pair 1 2 (indexes 4 to 5). Each one sums to 3. The method found all four with one pass.

Two details matter. The first is seen[0] = 1;, which counts the empty prefix. Without it, a subarray that starts at index 0 would never be counted. This is the same off-by-one idea as the prefix[0] entry in the range formula, and beginners miss it for the same reason. The second is the lookup with find instead of seen[prefix - k]. Writing seen[key] inside a lookup would create an entry with count 0 for every missing key, which slowly fills the table with junk. Use find when you only want to look, and [] when you want to insert or update.

The table uses long long for the keys, because prefix sums can grow large. An int key would overflow on long inputs, and the wrong answer would come with no warning.

What happens inside the prefix sum loop

The prefix sum build is a single pass with one addition and one store per element. The prefix array is read in order, so the processor's memory system handles it well, as it does for any linear scan. The query formula reads two entries, and both are at known positions, so the cost of a query is the same whether the range is short or long.

A hash table is different. The table stores its entries in buckets, and finding a key means computing a number from the key, called its hash, and looking in that bucket. On average the lookup takes constant time. In the worst case, with many keys in one bucket, it can take time proportional to the number of keys. Real libraries make that case rare, and for the course you can state the average cost. The interview answer is "O(n) on average, O(n) space for the table".

The space is worth stating too. The prefix array uses one entry per element, and the table can hold up to one entry per distinct prefix sum, so both are O(n) in the worst case. If the question allows it, a single running total with a table is the leanest answer you can give.

Choosing the right pattern from the wording

Most array problems reveal their pattern in the first sentence, if you know what to listen for. A short list of clues helps.

If the question asks for sums over many different ranges of the same array, think prefix sums. You build the row once, then answer each range with one subtraction. The phrase "from index a to index b" is the clue, and so is a question that repeats many times on the same data.

If the question asks for two values whose sum or product hits a target, and the array is sorted, think two pointers. The phrase "two values that add up to" with a sorted list is the clue. If the array is not sorted, ask whether you may sort it first. Sorting costs O(n log n), which is often far better than a nested loop. If you may not sort, a hash table can answer pair questions in O(n) on average.

If the question asks how many contiguous blocks have a property, and the values can be negative, think prefix sums with a hash table. The phrase "how many subarrays sum to exactly k" is the clue. A sliding two-pointer method works only when every value is positive, because moving the right end is then the only way to grow the sum. With negative values, the prefix and hash table method is the safe choice.

If the question asks for the best contiguous block, meaning the largest or smallest total, think Kadane's rule from the next lesson. If the block length is fixed, a sliding window is the simpler tool.

Before you choose, check two things. Is the array sorted? Can the values be negative? The answers to those two questions rule out most wrong patterns at once. A common interview mistake is to start coding the first idea that comes to mind. Spend thirty seconds naming the pattern, and the code follows faster and with fewer bugs.

Common mistakes and the wrong answers they cause

These mistakes rarely produce a compiler message. They produce wrong numbers, which is harder to spot. Learn to recognise them by the shape of the bug.

Forgetting the extra entry in prefix sums

If you build prefix with n entries instead of n + 1, the last range query reads past the end of the vector. If you build it with n + 1 entries but store the first value at prefix[0], every answer is off by one value. The rule is simple: prefix[0] is always 0, and prefix[k] is the sum of the first k values.

Using r where r + 1 belongs

The formula is prefix[r + 1] - prefix[l]. A version that writes prefix[r] - prefix[l] gives the sum of the values from l to r - 1, which drops the last value. The debugging walkthrough below traces this mistake with the sample array.

Overflowing an int

A sum of one hundred thousand values near one billion needs about 10 to the power of 14, and an int tops out near 2 times 10 to the power of 9. The program does not crash. It prints a number that is simply wrong. Use long long for any running total over a large input, and be suspicious of any answer that looks too small or too large.

Running two pointers on an unsorted array

The two-pointer pair search needs sorted data. On unsorted data, moving a pointer no longer tells you which direction the sum must go, so the program can skip the correct pair. Check the order before you choose the pattern. If the array is not sorted and you cannot sort it, the hash table version is the right tool.

Using [] to look up in a map

seen[key] inserts the key when it is missing. In a lookup, that quietly adds junk entries and can change later counts. Use find for a lookup and seen[key]++ only when you mean to record a value.

Forgetting the empty prefix

If the table does not start with the empty prefix (0, count 1), any subarray that begins at index 0 is missed. The answer is then too small, and the bug appears only for subarrays that start at the front. Test with a subarray that starts at the first value.

Debugging walkthrough: the range sum that is one short

A student writes the range formula as prefix[r] - prefix[l], and tests it on the array 3, 1, 4, 1, 5, 9 with the query from index 1 to 3. The expected answer is 6, which is 1 + 4 + 1. The program prints 5. The debugging method starts with the expected answer, and then asks what the program actually added.

Build the prefix row again: 0, 3, 4, 8, 9, 14, 23. The formula prefix[3] - prefix[1] is 8 minus 3, which is 5. The program added the values at indexes 1 and 2 only, which are 1 and 4. The value at index 3, the last value in the range, is missing. The reason is that prefix[3] is the sum of the first three values, indexes 0 to 2, and it does not include index 3. To include index 3, the formula needs prefix[4], which is the sum of the first four values.

The fix is the one in the program: use prefix[r + 1]. The general lesson is the one you should carry into every array problem. Check the boundaries of a formula with a tiny example. Choose a range with one value, such as indexes 1 to 1, and see whether the formula gives that value. A one-value range exposes the off-by-one error immediately.

Variations and edge cases

Negative values. Prefix sums still work. The running total can go down, and the range formula still gives the correct answer. Test with a range that contains only negatives.

Zeros. A run of zeros adds nothing, so consecutive prefix entries are equal. This matters in the subarray-count problem, because a zero-sum subarray is then counted once for each pair of equal prefix entries.

The full range. The query from 0 to n - 1 should give the total of the whole array, which is prefix[n]. Test it, because it is the easiest boundary to break.

An empty range. A range with l greater than r is not valid in the usual statement. If a problem allows it, define the answer as 0 and check the input before the formula.

Target zero. For the subarray-count problem with k equal to 0, the empty prefix is also relevant. The table already contains the empty prefix, so the answer counts every subarray whose sum is zero, and the trace in this lesson shows how.

Duplicates in the pair search. If the sorted array contains repeated values, the two-pointer count needs care. The program above stops at the first pair. A counting version has to skip equal values, or the same pair is counted twice. The practice exercise asks for distinct values to keep the idea clear.

Interview-style questions

Question: answer many range-sum questions quickly. Build a prefix sum array in one pass. Each query is one subtraction. State the total cost: O(n) to build and O(1) per query. Mention that the array is fixed. If the values change often, a structure called a Fenwick tree can update and query in O(log n), and the course covers that later.

Question: find two numbers in a sorted array that add up to a target. Two pointers, one at each end, O(n) time and O(1) extra space. Explain the rule for moving each pointer, and why it is safe, in one sentence per move.

Question: count the subarrays whose sum is exactly k. Prefix sums with a hash table, O(n) time on average and O(n) space. Explain the lookup of prefix - k, and say why the empty prefix starts the table.

Question: remove duplicates from a sorted array in place. The slow and fast pointers, O(n) time and O(1) extra space.

When you answer, name the pattern before you write the code. Interviewers often judge the choice of pattern more than the code itself, and naming it signals that you have seen the problem before.

Real-world uses

Prefix sums are everywhere in software that measures things over time or space. A banking app shows your balance after each transaction, which is a running total, and it uses the same subtraction to show what you spent in a month. Image editors compute a summed-area table, which is a two-dimensional prefix sum, so they can compute the average brightness of any rectangle in constant time. Analytics tools answer "total visitors from Monday to Friday" with the same formula. Finance code checks whether a window of prices has a total above a threshold, which is a subarray sum question.

Two pointers appear in sorting, merging and searching in sorted data. Merging two sorted lists into one uses two pointers, one in each list. Checking whether two sorted files share a line, or finding the closest pair of prices to a budget, uses the same movement. Recognising the pattern saves a nested loop, and a nested loop is often the reason a program is too slow for real data.

Practice

Try each exercise before you open the solution. Use the Run box to check your work. The first three are easy, the next four are medium, and the last is harder.

1. Given the array 5, 2, 8, 1, print the sum of the whole array and the sum of the middle two values, using prefix sums. The answers are 16 and 10.

2. Read n and k, then n values, and print the number of pairs of indexes (i, j) with i less than j where the two values add up to k, counting every pair even if values repeat. Test with 4 5 followed by 1 4 4 1. The answer is 4.

3. Print the number of values in a sorted array that are strictly greater than a given value x. Use the sorted array 1 3 3 6 9 and the value 3. The answer is 2.

4. Given the array 2, -1, 3, 4, -2, 5 and the query from index 1 to index 4, print the sum using prefix sums. The answer is 4.

5. Read a sorted array and a target, and print YES if any two values (different positions) add to the target, otherwise NO. Test with 5 12 followed by 1 3 5 8 11. The answer is YES, because 1 and 11 add to 12.

6. Read a sorted array and print the number of distinct values in it, without changing the array. Test with 6 followed by 2 2 3 3 3 7. The answer is 3.

7. Write a program that reads n and the values, and prints the length of the longest subarray whose sum is zero, or 0 if there is none. Test with 5 followed by 1 -1 2 -2 3. The longest zero-sum run is 1 -1 2 -2, length 4.

8. Prove in two sentences why moving left up is safe when the pair sum is smaller than the target in a sorted array.

9. Explain why prefix[r] - prefix[l] is wrong for an inclusive range, and give a two-line example that shows the error.

10. Write the subarray-count program from this lesson without the line seen[0] = 1;, then run it on 3 3 followed by 3 1 1. Explain why the answer changes.

What you now know

• A prefix sum array stores running totals, with prefix[0] equal to 0, so any inclusive range is prefix[r + 1] - prefix[l].
• Building the prefix row takes one O(n) pass, and each range query after that takes constant time.
• Two pointers moves two indexes by a rule, and each move discards values that cannot be part of an answer, so one pass solves the sorted pair search.
• The sorted-array rule must hold before you move a pointer. Unsorted data needs a different tool.
• The slow and fast pattern removes duplicates from a sorted array in place with O(1) extra space.
• Counting subarrays with a target sum uses a running prefix and a hash table, and it needs the empty prefix recorded at the start.
• Use long long for sums over large input, and always test the boundaries with a range of one value.