Solve Sorted-List Pair Sums with Two Pointers

Select a timestamp to watch that moment on YouTube.

1. 00:00

   We need two values from a sorted list whose sum is twelve. The list is one, three, five, nine. You can see three plus nine immediately, but pretend the list contains a million entries. We do not want to try every possible pair. Place one pointer at the start and another at the end. Add their values. The order of the list tells us which pointer can move safely. Before I run the code, pause and decide which pointer should move after one plus nine gives ten. The target is larger than ten, so we need to make the sum bigger. Keep that prediction in mind as we watch an intentionally broken implementation.

2. 00:40

   The two-pointer technique takes advantage of sorted order. Put one index at the smallest item and one at the largest. If their sum is below the target, only moving the left pointer right can increase it; if the sum is above the target, only moving the right pointer left can decrease it. Stop when the pointers meet. This visits at most one new pair per pointer movement, so the scan is linear in the number of values once the input is sorted. The function here returns a pair of values or None, not their original indices. The broken function sees a low sum and moves the right pointer toward smaller values. Its output is None even though three plus nine is present.

3. 01:23

   This is a subtle bug because the loop terminates normally and raises no exception. A test with target ten would pass immediately and hide it. A test with a target that requires moving a pointer exposes the mistaken branch. Notice that the function currently also assumes sorted input without checking it. We will focus on the pointer direction first, then make that precondition explicit. Whenever an algorithm relies on a property of its input, tests should include a case that actually requires that property. A tempting broken loop moves the right pointer left whenever a sum is too small. On [1, 3, 5, 9] with target 12, the first sum is 10.

4. 02:06

   Moving right left makes the next sum 6, then 4; the solution 3 plus 9 is skipped. Print the left value, right value, and sum on each iteration. The trace shows the sum drifting farther away from the target. This is a reasoning error about monotonicity, not a Python syntax error. Fix the direction of movement before adding any special-case branches. The trace prints candidate values and the current total. The first pair is one and nine, totaling ten. The broken move changes the right value to five, so the total drops to six. The next move changes it to three, totaling four.

5. 02:46

   We are moving away from twelve. The trace gives us an observation, but the fix needs a reason. Because one is the smallest remaining value and nine is the largest, pairing one with any other available number cannot raise the sum above ten. We can discard one. We should keep nine and move the left pointer from one to three. The next sum is exactly twelve. For an undersized sum, the smallest remaining value is already paired with the largest available value. Pairing it with an even smaller right value cannot reach a larger target, so discard that left value. The symmetric argument holds for an oversized sum: pairing the largest

6. 03:28

   remaining value with any larger left value cannot make the sum smaller, so discard the right value. This explains why the skipped pairs are safe to ignore. Repeated values remain separate positions, which allows [4, 4] to supply the pair (4, 4). A single [4] cannot reuse one item twice. The corrected scan implements that reasoning. When a sum is too small, left moves right; when a sum is too large, right moves left. When the pointers meet, no two distinct positions remain. The function returns the value pair when it finds the target and None otherwise. It also checks that the list is already ascending.

7. 04:10

   Sorting inside this function might be appropriate for a different contract, but here callers are told the requirement and an invalid input raises ValueError. The algorithm uses constant extra state. Each loop movement narrows the candidate interval, so at most a linear number of iterations occurs after the sorted list has been provided. Here is the invariant in plain language: if a low sum uses the smallest and largest remaining values, the smallest value cannot participate in any successful remaining pair. Moving left does not discard a solution. If a high sum uses the largest remaining value, no larger left-side partner can

8. 04:51

   lower it to the target, so moving right does not discard a solution either. This proof explains the one-way motion. We do not need a visited set or nested loop. The strict inequality between pointers prevents using the same position twice. The result is a tuple of values, so callers should use a different function if they require original indices from an unsorted input. Now test the boundaries. Two equal fours at different positions can reach eight; one four cannot be used twice. An empty list has no pair. An unsorted list must be rejected because pointer decisions are no longer justified by its order.

9. 05:33

   You can compare the function against a simple nested-loop solution on small arrays to build confidence, while keeping the faster scan in the final program. Try a negative target with negative sorted values and explain each pointer movement. The practical task checker covers a valid pair, no pair, duplicates, and invalid order. The quiz asks for the reasoning behind the movement, because memorizing the two branches without understanding them makes it easy to reverse the branches again. The task validates ascending order and rejects unsorted input because pointer movement would otherwise be unjustified.

10. 06:13

    Empty and one-item lists return None. If no pair exists, return None instead of inventing a nearest match. The algorithm is O(n) for an already sorted list and O(1) extra storage, apart from the pair returned. Sorting inside the function would change its input contract, runtime, and ability to preserve original indices, so this lesson keeps sorting as a documented precondition. Compare the result against a simple nested-loop oracle on small lists during testing.