Prefix sums and two pointers in Python

Why these two patterns matter

Many array questions look like they need a loop inside a loop. You check every start, then every end, then add up what is between them. That is correct, but it is slow. For a list of 100,000 values, a loop inside a loop can do billions of steps, and the program will take far too long to finish.

These two patterns turn many of those questions into one pass, or into a single build step followed by instant answers. Prefix sums spend a little time up front so every later question is fast. Two pointers use the order of a sorted list to skip pairs that cannot work. Both appear constantly in interviews, and both are short once you see the idea.

Part A: prefix sums

The problem that needs it

Suppose someone gives you a list of daily sales and then asks 1,000 questions, each of the form "what were the total sales from day l to day r?" The direct method adds up the values each time. A question about a range of 50,000 days costs 50,000 additions, and 1,000 questions cost 50 million additions. That is O(n) work per question, and O(n times q) in total, where q is the number of questions.

There is a better way, and it is the same idea as a bank statement.

The idea from first principles

A bank statement shows the running balance after each transaction. Line 1 shows the balance after the first payment, line 2 the balance after the second, and so on. If you want to know how much you spent between line 3 and line 7, you do not add up every purchase in between. You subtract the balance at line 2 from the balance at line 7. The subtraction removes everything before the start of your range.

A prefix sum array does exactly this for numbers in a list. Each entry stores the total of all values before it. Once that table exists, the total of any range is one subtraction.

Build the table once. Call the table prefix. Define prefix[i] as the sum of the first i values of the original list a. So prefix[0] is the sum of zero values, which is 0. prefix[1] is a[0]. prefix[2] is a[0] + a[1]. In general, prefix[i + 1] = prefix[i] + a[i], which is the running balance rule.

The table has length n + 1, not n. The extra leading 0 is what makes the formula work for every range, including ranges that start at index 0. You will see why in the next section.

For the list [2, 4, 1, 7, 3], the prefix table is [0, 2, 6, 7, 14, 17]. Each entry is the total of the values before it. Read it as: the first 0 values add to 0, the first 1 value adds to 2, the first 2 values add to 6, and so on.

The range formula

The sum of a[l] through a[r], with both ends included, is:

sum(l, r) = prefix[r + 1] - prefix[l]

Here is why. prefix[r + 1] is the total of everything from index 0 through index r. prefix[l] is the total of everything from index 0 through index l - 1. Subtracting removes the unwanted front part, a[0] through a[l - 1], and leaves exactly a[l] through a[r].

Take the list [2, 4, 1, 7, 3] again. The sum of indexes 1 to 3 is prefix[4] - prefix[1], which is 14 - 2 = 12. Check it by adding directly: 4 + 1 + 7 is 12. The two methods agree.

Worked example 1: many range queries

This program reads a list and then a list of questions. Each question is a pair l r, and the program prints the sum from l to r. It is the full pattern in its natural form: one build, then many instant answers.

The input has three parts. The first line holds n. The second line holds the n values. The third line holds the number of questions q, and the next q lines each hold one l r pair. Save the program as main.py, run it with python3 main.py, and type the input lines as they appear here: 5, then 2 4 1 7 3, then 3, then 1 3, then 0 4, then 2 2.

n = int(input())
a = [int(x) for x in input().split()]
 
prefix = [0] * (n + 1)
for i in range(n):
    prefix[i + 1] = prefix[i] + a[i]
 
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(prefix[r + 1] - prefix[l])

Output:

12
17
1

Trace the three questions. The question 1 3 asks for a[1] + a[2] + a[3], which is 4 + 1 + 7 = 12. The formula gives prefix[4] - prefix[1] = 14 - 2 = 12. The question 0 4 covers the whole list. The formula gives prefix[5] - prefix[0] = 17 - 0 = 17. The question 2 2 asks for one value, a[2]. The formula gives prefix[3] - prefix[2] = 7 - 6 = 1. A range of one element is a valid range, and the formula handles it with no special case.

The line l, r = map(int, input().split()) reads two numbers from one line. map(int, ...) applies int to each piece of text, and the two names on the left take the two results in order.

Python has a shorter way to build the table. itertools.accumulate returns the running totals, and [0, *accumulate(a)] puts the leading 0 in front. The loop above shows the rule, and the one-line version is what you will see in real code.

Output:

[0, 5, 10, 15, 20]
10

The cost is O(n) to build the table once, and O(1) per question. Each question does one subtraction and two list lookups, whatever the size of the range. The memory is O(n) for the table.

Python integers do not overflow, so the table needs no special type for large sums. In a language with fixed-size integers, the table would need a 64-bit type for big sums. The first lesson of this module explains the difference.

It helps to compare this with the obvious alternative. Without a prefix table, each question adds up its own range, so the total cost is the sum of all the range lengths, which can be n times q in the worst case. With the table, the cost is n for the build plus a constant amount for each question, so the total is about n plus q. For 100,000 days and 100,000 questions, that is the difference between 10 billion additions and about 200,000 steps. The table is a small cost paid once, and after that the questions are almost free.

Be careful with the bounds. r + 1 must be at most n, which means r must be at most n - 1. A question with r equal to n reads past the table and raises IndexError.

Subarray sums with a running total

A second use of prefix sums is more subtle, and it is a favourite interview problem. The question is: how many subarrays add up to exactly k? A subarray is a continuous slice, as the Kadane lesson explains. Values can be negative, which rules out a simple two-pointer approach. The values might not be sorted, so there is no order to exploit.

Here is the key observation. A subarray from index i to index j - 1 has sum prefix[j] - prefix[i]. You want that to equal k. Rearrange the equation: prefix[i] = prefix[j] - k. So, as you walk through the list and reach position j, you need to know how many earlier prefix values equal prefix[j] - k. Each such earlier value marks a start position that makes a subarray with sum k ending just before j.

A dict (a dictionary) answers "how many times have I seen this value?" in O(1) average time. A dict maps each key to a value, so here the key is a prefix total and the value is how many times it has appeared. Walking the list, you add the count for running - k to the answer, and then you record the current running total. This makes the whole job one pass.

One detail is easy to forget. The empty prefix, with value 0, must be in the dict before you start. Otherwise, a subarray that starts at index 0 is never counted. Start the dict as seen = {0: 1}.

Worked example 2: counting subarrays with sum k

Save the program as main.py and type 5, then 1 2 3 -2 4, then 3, one line each.

n = int(input())
a = [int(x) for x in input().split()]
k = int(input())
 
seen = {0: 1}
running = 0
count = 0
for value in a:
    running += value
    count += seen.get(running - k, 0)
    seen[running] = seen.get(running, 0) + 1
print(count)

Output:

3

The method seen.get(key, 0) returns the count for key, or 0 when the key is not in the dict. Reading a missing key with seen[key] raises KeyError instead, so get is the safe choice here. The standard library also has collections.Counter, which returns 0 for a missing key on its own.

Trace it with the numbers. The running totals after each value are 1, 3, 6, 4, 8. Before the loop the dict holds {0: 1}.

For a[0] = 1, the running total is 1. The key 1 - 3 = -2 is not there, so add nothing. Store 1: 1.

For a[1] = 2, the running total is 3. The key 3 - 3 = 0 is in the dict once, so add 1. That count is the subarray 1, 2, which sums to 3. Store 3: 1.

For a[2] = 3, the running total is 6. The key 6 - 3 = 3 is in the dict once, so add 1. That is the subarray 3 on its own. Store 6: 1.

For a[3] = -2, the running total is 4. The key 4 - 3 = 1 is in the dict once, so add 1. That is the subarray 2, 3, -2. Store 4: 1.

For a[4] = 4, the running total is 8. The key 8 - 3 = 5 is not there, so add nothing. The total count is 3.

The dict is the speed trick. A naive solution checks every pair of positions, which is O(n squared). This one checks one key per position, so it runs in O(n) average time and O(n) memory for the dict.

Part B: two pointers

The idea

The second pattern works on a sorted list. Place one pointer at the left end and one at the right end. A pointer here is just an index variable that marks a position. Compare the two values, then move one pointer inward. Repeat until the pointers meet.

Take the question "is there a pair of values that adds up to a target?" Start with the smallest value on the left and the largest on the right. If their sum is too big, the right value is too large for any pair with the current left value, so move the right pointer one step left. If the sum is too small, the left value is too small, so move the left pointer one step right. Each move discards a value that cannot be part of a valid pair.

Why is it safe to throw values away? Because the list is sorted. Moving the left pointer right can only make the sum bigger. Moving the right pointer left can only make it smaller. The pointers therefore sweep toward the answer without skipping it. If a valid pair exists, the pointers reach it.

Here is an everyday version. Imagine two people searching for a pair of shoes that add up to a budget. Both lists are sorted by price. The first person starts with the cheapest left shoe and the second person starts with the most expensive right one. If the total is over budget, the second person moves to a cheaper shoe. If under budget, the first person moves to a dearer one. They never need to check each pair in full.

Worked example 3: a pair with a given sum

Save the program as main.py and type 6, then 1 3 4 6 9 11, then 10, one line each.

n = int(input())
a = [int(x) for x in input().split()]
target = int(input())
 
left = 0
right = n - 1
while left < right:
    total = a[left] + a[right]
    if total == target:
        print(a[left], a[right])
        break
    elif total < target:
        left += 1
    else:
        right -= 1
else:
    print("NO")

Output:

1 9

This program uses a while loop with an else part. The else block runs only when the loop ends because its test became false. It does not run when the loop stops at a break. So the NO line prints only when no pair was found. Many Python programmers find this easier to read than a flag variable.

Trace it. The pointers start at 0 and 5, with values 1 and 11. Their sum is 12. That is bigger than 10, so right moves to index 4, with value 9. Now the sum is 1 + 9 = 10, which is the target. The program prints 1 9 and stops.

Notice that the program never looked at the pair 3 and 11, or 4 and 9. It skipped them correctly. Once right moved past 11, the value 11 could never pair with a left value to make 10, because every left value from now on is at least 1 and 1 + 11 is already too big. The sorted order is what makes that reasoning true.

If you change the target to 2, the program prints NO. Try it in your head first: the two smallest values sum to 4, which is already above 2, so no pair can work.

The loop runs at most n steps, because each step moves one pointer by one and the pointers never move back. The time is O(n). The memory is O(1), since the program keeps only two indexes and a sum.

Worked example 4: removing duplicates in place

The second big use of two pointers is editing a sorted list in place. The task is to remove repeated values so each value appears once, keeping the order, and to report how many distinct values remain. You can delete items from a Python list with del or pop, but each delete shifts the later items, which costs O(n) each time. The trick here is to overwrite the front of the list with the distinct values and ignore the rest, which costs O(n) in total.

Use two indexes. The read index walks through every box. The write index marks where the next distinct value belongs. A value is new when it differs from the value just before the write position. Copy new values to write and advance it.

Save the program as main.py and type 7, then 0 0 1 1 1 2 3, one line each.

n = int(input())
a = [int(x) for x in input().split()]
 
if n == 0:
    print(0)
else:
    write = 1
    for read in range(1, n):
        if a[read] != a[write - 1]:
            a[write] = a[read]
            write += 1
    print(write)
    print(a[:write])

Output:

4
[0, 1, 2, 3]

Trace the list 0 0 1 1 1 2 3. The first value is always kept, so write starts at 1. The read index moves through the rest. At read = 1, the value 0 equals a[0], so it is skipped. At read = 2, the value 1 differs from a[0], so it is copied to a[1] and write becomes 2. The next two 1s are skipped because they equal a[1]. The value 2 is copied to a[2], and the value 3 to a[3]. The final write is 4.

The list is now [0, 1, 2, 3, 1, 2, 3] in memory, with the first four boxes correct. The last three boxes hold leftover values, which is why the program prints only the first write boxes with the slice a[:write]. A slice a[start:end] is a new list of the boxes from start up to, but not including, end. A missing start means 0, and a missing end means the end of the list.

Why compare with a[write - 1] and not with a[read - 1]? Because a[read - 1] may already have been overwritten. The value that matters is the last distinct value you kept, and that sits at write - 1.

This is O(n) time and O(1) extra space. The same skeleton solves "move all zeros to the end" from the practice set in the first lesson.

If you only need the distinct values in a new list, Python has a shorter way that keeps the order: list(dict.fromkeys(a)). A dict cannot hold the same key twice, so the duplicates drop out, and the dict keeps insertion order. That version makes a new list, while the two-pointer version changes the list in place.

Worked example 5: checking a palindrome

A palindrome reads the same forwards and backwards, such as 1 2 3 2 1. Compare the first and last values, then the second and the second-last, and so on, moving inward. Two pointers do this with no extra memory.

Output:

YES

Change the list to [1, 2, 2, 3], and the output is NO. The first pair, 1 and 3, differs, so the loop stops at once.

Python also has a one-line check: a == a[::-1]. The slice a[::-1] makes a reversed copy, because a step of -1 walks the list backwards, and the comparison looks at every value. It is clear and fine for short lists. It uses O(n) extra memory for the copy, while the two-pointer loop uses O(1), so the loop is the better choice when the list is large.

The loop stops when the pointers meet or cross. For an odd length such as 5, the middle box at index 2 is never compared, because both pointers stop on it. For an empty list, right is -1, the loop test left < right is false immediately, and the answer is YES, which is the agreed answer for an empty palindrome.

Why two pointers never miss a valid pair

A method is only useful if you can trust it, so here is a short argument that two pointers find a pair whenever one exists. Suppose a valid pair sits at positions i and j, with i before j, so that a[i] + a[j] equals the target T. Because the list is sorted, every value at or before position i is no bigger than a[i], and every value at or after position j is no smaller than a[j].

Start with the right pointer. While the left pointer is at i or before it, the sum a[left] + a[j] is at most T, because a[left] is no bigger than a[i]. So when the right pointer reaches j, the sum is never above T. The rule "move the right pointer left when the sum is too big" never fires at j, so the right pointer stays at j or further right.

Now the left pointer. While the right pointer is at j or after it, the sum a[i] + a[right] is at least T, because a[right] is no smaller than a[j]. So when the left pointer reaches i, the sum is never below T. The rule "move the left pointer right when the sum is too small" never fires at i, so the left pointer stays at i or before it.

These two facts keep both pointers on their sides of the pair for as long as the loop runs. The loop ends in one of two ways. Either the sum equals T, and a pair is found, or the pointers cross. The pointers cannot cross while i is before j, because the left pointer never passes i, and the right pointer never passes j. Since each pointer moves one step at a time, if no earlier pair exists, the left pointer must reach i. At that point the sum is exactly T, so the method stops with the pair.

The argument uses the sorted order twice, once for each side. If the list is not sorted, the claim that every value before i is no bigger than a[i] is false, and the proof falls apart. That is the reason for the sorted requirement in the first place.

You can test the argument on a small case. Take [1, 3, 4, 6, 9, 11] with target 10, where the pair is 1 and 9 at positions 0 and 4. The right pointer moves from 5 to 4 and stops there, because the sum at 4 is exactly 10. The left pointer never needed to move, which fits the claim that the pair is reached without passing it.

Choosing between the patterns

A quick way to decide which tool to reach for:

• The question asks for a sum over a range, and the list will be queried many times without changing: build a prefix sum list.
• The question asks for a sum or count of subarrays, and values can be negative: use prefix sums with a dict of counts.
• The question asks for a pair or a set of values with a target, and the list is sorted or can be sorted: use two pointers.
• The question asks you to rewrite a sorted list with duplicates or unwanted values removed: use a read index and a write index.
• The question asks about a maximum or minimum over subarrays with no order given: that is Kadane, from the next lesson.

Sorting an unsorted list first costs O(n log n) time. That is often worth it, because the two-pointer pass after it is O(n). But sorting changes the indexes, so if the question asks for positions in the original list, use sorted(a) to make a sorted copy and keep the original list for the positions.

Common mistakes

1. A prefix list of length n. With length n, the query prefix[l - 1] fails or misreads when l is 0. Use length n + 1 with a leading 0, and the formula works for every range. The debugging walkthrough below shows what goes wrong with length n.

2. Mixing up inclusive and exclusive ends. The formula prefix[r + 1] - prefix[l] treats r as included. If a question says "from l up to but not including r", the formula becomes prefix[r] - prefix[l]. Decide once, write it on paper, and check with a one-element range.

3. Forgetting the 0 in the dict. Without seen = {0: 1}, subarrays that start at index 0 are missed. Test with the list [3] and k = 3. The answer should be 1, and without the initial 0 the program prints 0.

4. Using two pointers on an unsorted list. The rule "moving left up increases the sum" only holds when the list is sorted. On [5, 1, 4] with target 9, the pointers see 5 and 4, the sum is 9, and the answer happens to be right. But on [1, 9, 2, 8] with target 10, the pointers see 1 and 8, which sums to 9, and move left to 9. They then see 9 and 8, which sums to 17, move right to 2, and see 9 and 2, which sums to 11, so they move right again and stop. The pair 1 and 9 does sum to 10, but the pointers never compare those two values, so the program prints NO when the answer is yes. Sort first or use a dict.

You can check this case yourself.

Output:

None
(1, 9)

The first call misses the pair because the list is not sorted. Sorting it first makes the same method work.

5. Missing a pointer move. Every branch of the if must move a pointer, or the loop never ends. If you write if total < target: left += 1 and forget the else branch, the loop runs forever on a large sum. Python does not stop it for you, so you must press Ctrl+C in the terminal to stop the program.

6. Expecting an overflow error in sums. Python integers grow to any size, so a[left] + a[right] never wraps around to a negative number. The risk moves elsewhere. Very large numbers take more memory and more time, and a list of huge numbers can be slow. Other languages need a long type for large sums, which is a different rule.

Debugging walkthrough: a prefix sum that is wrong by one

Here is a bug that often appears in code reviews. A program builds a prefix list of length n instead of n + 1, and answers a query for l = 0.

Output:

[2, 6, 7, 14, 17]
-10

The correct answer is 7, which is 2 + 4 + 1. The program prints -10 and raises no error. The reason is that l - 1 is -1, and Python reads a negative index from the end of the list. So prefix[-1] is the last value, 17, and the subtraction becomes 7 - 17 = -10. Other languages would raise an error here, but Python hides the mistake by design, so a wrong answer can look normal.

The bug is the choice of the query formula. The formula needs an entry for "everything before l", and for l = 0 that entry is the empty prefix, which must be 0. The table in this version has no slot for it. The fix is the length n + 1 build from Part A, where prefix[0] is 0 and the formula prefix[r + 1] - prefix[l] works for every l.

The method to follow when you debug a wrong answer like this is always the same. Write down the index that was used, the valid range, and the smallest input that reaches the line. For this bug the smallest input is l = 0, which gives a wrong answer at once. Watch for negative indexes in particular, because Python accepts them without a warning.

Variations and related problems

Once the two patterns are clear, many variations follow the same steps.

Container with the most water. You have a row of vertical lines. Choose two lines, and the water they hold is the smaller height times the distance between them. Put pointers at both ends. Move the pointer at the shorter line inward, because the water is limited by the shorter side. This is a famous two-pointer problem, and the reason for moving the shorter side is the same kind of argument as before.

Three-sum. Find three values that add up to zero. Sort the list, fix one value, and run a two-pointer search on the rest. This turns an O(n cubed) search into O(n squared).

Sliding window. When all values are positive, a window of values can grow on the right and shrink on the left. This is a two-pointer method in which both pointers move in the same direction. It answers questions such as "longest subarray with sum at most k" in one pass. With negative values, the window idea fails, and the dict approach from Part A is used for exact-sum counts instead.

Range queries on changing data. The prefix table is fast only when the values do not change. If an update changes one value, every later prefix entry is wrong, and rebuilding the table costs O(n). Later modules cover segment trees, which are built for updates.

Interview-style questions

"Why does the prefix sum give O(1) per query?" Because the table is built once in O(n), and then any range is one subtraction of two stored values. The work per query does not depend on the range length.

"Why does two pointers need a sorted list?" Because moving the left pointer right can only increase the sum, and moving the right pointer left can only decrease it. Those two facts let each move discard values safely. Without sorting, a move might skip the only valid pair.

"Why is the total time O(n) and not O(n squared)?" Each pointer only moves in one direction, and it moves at most n times. Two pointers together do at most about 2n steps.

"How do you count subarrays with sum k when there are negative numbers?" Use prefix sums with a dict of counts, and remember that the empty prefix 0 is seen once at the start.

A strong answer states the cost, the condition the method depends on, and the edge case it must handle, such as the empty prefix or an empty list.

Real-world uses

Prefix sums sit behind many everyday features. A spreadsheet's running total column is a prefix sum. A chart that shows "total so far" is one. A system that counts requests in the last N seconds often keeps running totals so each query is a subtraction. Image processing uses a two-dimensional prefix sum table, the matrix version of this idea, to compute the total brightness of any rectangle at once.

Two pointers appear in search features, in merging sorted lists, and in checking pairs of records against a budget or a limit. The palindrome check is a basic step in text tools and in validating codes.

Practice

Try each one before you read the answer. Save each program as main.py and run it with python3 main.py.

1. Build the prefix list for [5, 5, 5, 5] by hand, and use it to find the sum of indexes 1 to 2. The answer is 10. Write the prefix table with its indexes before you check.

Show the answer

The prefix list is [0, 5, 10, 15, 20]. The sum of indexes 1 to 2 is prefix[3] - prefix[1], which is 15 - 5 = 10. Check by adding: 5 + 5 = 10.

2. Given the sorted list [2, 5, 8, 12] and target 13, trace the two pointers by hand and write the pair. The answer is 5 8, because 5 + 8 = 13.

Show the answer

The pointers start at 2 and 12. Their sum is 14, which is too big, so right moves to 8. The sum 2 + 8 is 10, which is too small, so left moves to 5. The sum 5 + 8 is 13, which is the target. The pair is 5 8.

3. Write a function that returns True if a list reads the same forwards and backwards, using two pointers. Test it with [1, 2, 1] and [1, 2, 3].

Show the answer

The output is True and then False. The function returns as soon as a mismatch is found, so it does not need the break used in the worked example.

4. Given [3, -1, 4, -2, 5], find the sum of indexes 1 to 3 using a prefix list. The answer is 1.

Show the answer

The prefix list is [0, 3, 2, 6, 4, 9]. The sum is prefix[4] - prefix[1] = 4 - 3 = 1. Check by adding: -1 + 4 + -2 = 1.

5. Count how many subarrays of [1, 1, 1] sum to 2. The answer is 2 ([1, 1] at positions 0 to 1, and at positions 1 to 2). Then run the dict program from worked example 2 on the same input with k set to 2, and confirm it prints 2.

Show the answer

Running totals are 1, 2, 3. The dict starts as {0: 1}. At the first value the key 1 - 2 = -1 is missing, so nothing is added, and the dict becomes {0: 1, 1: 1}. At the second value, the running total is 2 and the key 0 is present once, so one subarray is added. The dict becomes {0: 1, 1: 1, 2: 1}. At the third value, the running total is 3 and the key 1 is present once, so one more is added. The total is 2.

6. Write a program that reads n, then a sorted list, then a target, and prints the number of index pairs whose sum is exactly the target. Duplicate values count as separate boxes. Test with 5, then 1 1 1 2 3, then 4. The answer is 3, because the three 1s each pair with the 3.

Show the answer

n = int(input())
a = [int(x) for x in input().split()]
target = int(input())
 
count = 0
left = 0
right = n - 1
while left < right:
    total = a[left] + a[right]
    if total < target:
        left += 1
    elif total > target:
        right -= 1
    elif a[left] == a[right]:
        k = right - left + 1
        count += k * (k - 1) // 2
        break
    else:
        lv, rv = a[left], a[right]
        lc = rc = 0
        while left < n and a[left] == lv:
            left += 1
            lc += 1
        while right >= 0 and a[right] == rv:
            right -= 1
            rc += 1
        count += lc * rc
print(count)

When both ends hold the same value, every value between them is equal too, so all the remaining pairs are counted at once and the break is correct. When the two ends differ, the program counts the run of equal values on each side and multiplies the two run lengths. Test it against a slower method that checks every pair of indexes, and both agree on random inputs.

7. Find the largest product of two values in a sorted list, using the two ends. Test with [-10, -3, 1, 4, 6]. The answer is 30, from -10 * -3, which beats 4 * 6 = 24. Explain in one sentence why checking only the two ends is enough.

Show the answer

The largest product is either the two largest values or the two most negative values, because two negatives make a positive. Those four values sit at the two ends of the sorted list. The sentence is: the two ends hold the most extreme values, so the best product must use one of those ends.

Output:

30

8. Remove every occurrence of the value 0 from a list, keeping the order of the other values, and print the new length and the new values. Input 6, then 3 0 4 0 0 5. The answer is 3, and the first three boxes are 3 4 5.

Show the answer

n = int(input())
a = [int(x) for x in input().split()]
 
write = 0
for read in range(n):
    if a[read] != 0:
        a[write] = a[read]
        write += 1
print(write)
print(a[:write])

The output is 3 and then [3, 4, 5]. The same read and write pattern as worked example 4 removes a value wherever it appears, not only duplicates. A shorter version, kept = [v for v in a if v != 0], gives the same values in a new list.

9. A program uses prefix[r] - prefix[l] to get the sum of a[l..r] inclusive. Find the bug, and give the corrected formula.

Show the answer

The bug is that the formula is off by one. prefix[r] holds the sum of the first r values, which is a[0] through a[r - 1]. It excludes a[r], so the range is missing its last value. The corrected formula prefix[r + 1] - prefix[l] includes a[r]. Check with [2, 4, 1] and l = 0, r = 1: the correct answer is 6, and the old formula gives prefix[1] - prefix[0] = 2.

10. Explain why two pointers cannot solve "find a pair with sum 10" on the unsorted list [1, 9, 2, 8], and say which tool you would use instead.

Show the answer

The pointers see 1 and 8 first, which sum to 9, so the left pointer moves right to 9. Then 9 and 8 sum to 17, so the right pointer moves left to 2. Then 9 and 2 sum to 11, so the right pointer moves left again, to the 9 at index 1, where the left pointer already sits. The loop ends. The pair 1 and 9 is never compared. The fix is to use a dict that records the values already seen, which finds the pair in O(n) time, or to sort first, which costs O(n log n) time.

What you now know

• A prefix sum list stores running totals, with length n + 1 and a leading 0.
• The sum of a[l..r] is prefix[r + 1] - prefix[l]. The table costs O(n) to build, and each query costs O(1).
• Counting subarrays with sum k uses prefix sums plus a dict of counts, and the empty prefix 0 must be counted once at the start.
• Two pointers on a sorted list find pairs with a target in O(n) time, because each move discards values that cannot work.
• A read index and a write index edit a list in place, and the same pattern removes any unwanted value.
• Check whether a list is sorted before you use two pointers, and check the empty list and the one-element list as edge cases.
• Python accepts negative indexes without an error, so a wrong index such as -1 can give a wrong answer with no warning.