Two pointers from both ends

Sorting often unlocks a faster scan. Put one pointer at the left end and one at the right end of a sorted list, and move them toward each other.

lo, hi = 0, len(w) - 1
while lo < hi:
    if w[lo] + w[hi] > limit:
        hi -= 1        # too big: the largest must go
    else:
        lo += 1        # fits: move up the small side

Each step throws away work that cannot matter. In a sorted list, if the biggest value is too much for the smallest partner, it is too much for every partner. One pass over n items replaces checking every pair, which is n * n steps.

Two things to remember: sorted(items) first when the input is not sorted, and always say what lo < hi guarantees (two different positions).

Watch the highlighted cell: it is the left pointer lo. The right pointer hi moves in from the far end.

See it run

w = [1, 3, 4, 8, 11]
lo = 0
hi = 4
while lo < hi:
    if w[lo] + w[hi] > 10:
        hi -= 1
    else:
        lo += 1

The list is sorted. The highlight shows lo; hi starts at the opposite end. We want pairs with a sum of at most 10.

Practice two pointers from both ends

Exercise 1

A secret code reads the same in a mirror if its first character equals its last, its second equals its second-to-last, and so on. Write solution(code) to return how many mirror pairs differ.

Rules:

A mirror pair is the characters at positions i and len(code) - 1 - i, counting each pair once (so only i from the left half).
The middle character of an odd-length code has no partner and is ignored.
Return an integer. An empty string, or one character, gives 0.
Letters are compared exactly (case matters).

Constraints: 0 ≤ len(code) ≤ 10^5.

Example: solution("abca") returns 1: the outer pair a and a match, the inner pair b and c differ.

Exercise 2

A shop wants to know which two-item bundles hit a spending target. Write solution(prices, target) to pick two different items (two different positions in the list) and return the bundle total that is closest to target.

Rules:

Items at different positions may have equal prices.
If two possible totals are equally close to target, return the smaller total.
prices has at least 2 items, all positive integers. Return an integer.

Constraints: 2 ≤ len(prices) ≤ 10^4; prices and target up to 10^6.

Example: solution([4, 9, 2, 15], 12) returns 11. The totals 13 (4+9) and 11 (9+2) are both 1 away from 12, so the smaller one, 11, wins.

Exercise 3

A cafe lets customers pick two different items from the menu as a combo. Write solution(prices, budget) to return how many combos cost at most budget in total.

Rules:

A combo is a pair of different positions i < j; two items with the same price are still different items.
The pair (i, j) and (j, i) are the same combo and count once.
Return an integer; it is 0 if no pair fits.

Constraints: 2 ≤ len(prices) ≤ 10^5; prices and budget are integers from 1 to 10^9. Your solution must be fast on 10^5 items.

Example: solution([3, 1, 5, 2], 6) returns 4: the combos 3+1, 3+2, 1+5 and 1+2 fit; 3+5 and 5+2 do not.

The explanation and tasks are public. Running this lesson requires an account with course access.

Practice

Loading Python…

Loading exercise content…

Visualizer Watch your code run line by line

Run your code, then choose Play to follow its execution.

Memory · names → values

Variables appear here as Python creates them.

Output & plots