PART 4 · DSA AND COMPLEXITY · CHAPTER 18

Arrays and strings: two pointers, prefix sums

FreeLesson 43 of 78

Two pointers walk through the data from two positions at once. They turn many O(n²) "check every pair" problems into a single O(n) pass.

PAIR WITH A TARGET SUM IN A SORTED LISTPYTHON 3.12

def pair_with_sum(sorted_amounts, target):
    i, j = 0, len(sorted_amounts) - 1
    while i < j:
        s = sorted_amounts[i] + sorted_amounts[j]
        if s == target:
            return sorted_amounts[i], sorted_amounts[j]
        if s < target:
            i += 1            # need a bigger sum: move left up
        else:
            j -= 1            # need a smaller sum: move right down
    return None

amounts = sorted([1198, 796, 1499, 1999, 1348, 1048, 747, 3498])
print(amounts)
print(pair_with_sum(amounts, 2847), pair_with_sum(amounts, 5))

Output

[747, 796, 1048, 1198, 1348, 1499, 1999, 3498]
(1348, 1499) None

READ AND WRITE POINTERSPYTHON 3.12

def dedupe_sorted(xs):            # in place, O(1) extra
    if not xs:
        return 0
    write = 1
    for read in range(1, len(xs)):
        if xs[read] != xs[write - 1]:
            xs[write] = xs[read]
            write += 1
    del xs[write:]
    return write

ids = [101, 101, 102, 103, 103, 103, 105]
print(dedupe_sorted(ids), ids)

Output

4 [101, 102, 103, 105]

POINTERS FROM BOTH ENDSPYTHON 3.12

def is_palindrome(s):
    i, j = 0, len(s) - 1
    while i < j:
        if not s[i].isalnum():
            i += 1
        elif not s[j].isalnum():
            j -= 1
        elif s[i].lower() != s[j].lower():
            return False
        else:
            i, j = i + 1, j - 1
    return True

print(is_palindrome("Was it a car or a cat I saw?"),
      is_palindrome("prepnplaced"))

Output

True False

PREFIX SUMS AND PARSING WITHOUT REGEXPYTHON 3.12

from itertools import accumulate

changes = [5, -2, -8, 3, 4, -1, 6, -9]     # daily change in signups
running = list(accumulate(changes))
print("running total:", running)
print("lowest point after day", running.index(min(running)) + 1)

s = "2025-04-01 02:00:05 WARN job=orders_daily"
date, time_, level, job = s.split(maxsplit=3)
print(date, level, job.partition("=")[2])

Output

running total: [5, 3, -5, -2, 2, 1, 7, -2]
lowest point after day 3
2025-04-01 WARN orders_daily

split(maxsplit=3) stops after three cuts, so the rest of the line stays whole. partition always returns three parts, so it never raises on a missing "=" the way unpacking a split can.

Practice before you move on

Use two pointers on the sorted amounts of orders.csv to find two orders that add up to a total you choose.
Build prefix sums over a list of daily revenue and answer the total between two days in one step.