Unit 14 — Two Pointers & Sliding Window

A school store has a SORTED list of prices and a fixed budget: can two prices spend it exactly without testing every pair? And what is the longest run of days whose total training stays under a limit? Both become LINEAR when two indices move forward with a clear rule. We build it as a short ladder of executable demos with a Notice, then a full stdin solver.

You will learn

Move two pointers inward on a sorted list to find a pair with a given sum.
Track the closest sum while the pointers converge.
Slide a window with a running sum to find the longest or shortest run that meets a rule.
Explain why both patterns take O(n) steps.

Lesson 1 — Converging Two Pointers

On a SORTED list, start lo at the front and hi at the back. If the pair sum is too small, move lo up; too big, move hi down; equal, done.

values = [1, 4, 6, 9, 11]
target = 15
lo = 0
hi = 4
found = False
while lo < hi and found == False:
    total = values[lo] + values[hi]
    print("check", values[lo], "+", values[hi], "=", total)
    if total == target:
        found = True
    elif total < target:
        lo = lo + 1
    else:
        hi = hi - 1
print(found)

Output

check 1 + 11 = 12
check 4 + 11 = 15
True

Notice

1 + 11 = 12 is too small → move lo up; 4 + 11 = 15 — found. The pointers CONVERGE; no pair is tested twice.

The same sweep can track the CLOSEST sum instead of an exact match.

values = [1, 4, 6, 9]
target = 12
lo = 0
hi = 3
best = 999
while lo < hi:
    total = values[lo] + values[hi]
    gap = abs(total - target)
    if gap < best:
        best = gap
    if total < target:
        lo = lo + 1
    else:
        hi = hi - 1
print("closest gap", best)

Output

closest gap 1

Notice

Keep the smallest gap seen while converging; here the closest sum to 12 is off by 1.

Why is it O(n)? Each pointer only ever moves ONE way, so together they take at most n steps — count them.

values = [2, 4, 6, 8, 10, 12]
target = 100
lo = 0
hi = 5
moves = 0
while lo < hi:
    total = values[lo] + values[hi]
    if total < target:
        lo = lo + 1
    else:
        hi = hi - 1
    moves = moves + 1
print("pointer moves:", moves, "for n =", len(values))

Output

pointer moves: 5 for n = 6

Notice

The two pointers make n - 1 = 5 moves total before meeting — linear, not quadratic.

Put it together: the program reads N, a target, then the N ALREADY-SORTED values, and prints YES if two of them sum to the target, else NO.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
target = int(tokens[1])
values = []
i = 0
while i < n:
    values.append(int(tokens[i + 2]))
    i = i + 1

answer = "NO"
lo = 0
hi = n - 1
while lo < hi and answer == "NO":
    pair_sum = values[lo] + values[hi]
    if pair_sum == target:
        answer = "YES"
    elif pair_sum < target:
        lo = lo + 1
    else:
        hi = hi - 1
print(answer)

Run the full solver from this unit folder:

python assets/l1.py < assets/l1/1.in

Notice

Converge lo/hi on the sorted list; a found-style flag stops the loop when the pair sum equals the target.

Complexity: O(n) — the input is already sorted, so no sort is needed.

Lesson 2 — Sliding Windows

A window [left, right] grows by adding values[right]; keep a RUNNING SUM instead of re-adding. This needs NON-NEGATIVE values so shrinking is safe.

values = [5, 2, 1, 1, 3]
window_sum = 0
right = 0
while right < len(values):
    window_sum = window_sum + values[right]
    print("added", values[right], "-> window sum", window_sum)
    right = right + 1

Output

added 5 -> window sum 5
added 2 -> window sum 7
added 1 -> window sum 8
added 1 -> window sum 9
added 3 -> window sum 12

Notice

window_sum accumulates as right advances (5, 7, 8, 9, 12) — one add per step, no re-summing.

Shrink from the LEFT while the window is over budget; the widest window seen is the longest affordable stretch.

values = [5, 2, 1, 1, 3]
limit = 7
left = 0
window_sum = 0
best = 0
right = 0
while right < len(values):
    window_sum = window_sum + values[right]
    while window_sum > limit and left <= right:
        window_sum = window_sum - values[left]
        left = left + 1
    length = right - left + 1
    if length > best:
        best = length
    right = right + 1
print("longest affordable window:", best)

Output

longest affordable window: 4

Notice

When the sum exceeds 7, drop values[left] and advance left; the widest window within budget here is 2 1 1 3 (sum 7), length 4.

Reverse the goal: shrink while the window MEETS a target to find the SHORTEST qualifying window.

values = [2, 3, 1, 2, 4]
target = 6
left = 0
window_sum = 0
shortest = len(values) + 1
right = 0
while right < len(values):
    window_sum = window_sum + values[right]
    while window_sum >= target and left <= right:
        length = right - left + 1
        if length < shortest:
            shortest = length
        window_sum = window_sum - values[left]
        left = left + 1
    right = right + 1
print("shortest reaching target:", shortest)

Output

shortest reaching target: 2

Notice

Once the sum reaches 6, shrink to record the shortest length; here it is 2 (2 4).

Put it together: the program reads N, a limit, then the N non-negative values, and prints the LONGEST window whose sum stays <= limit.

Try it yourself

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
limit = int(tokens[1])
values = []
i = 0
while i < n:
    values.append(int(tokens[i + 2]))
    i = i + 1

left = 0
right = 0
window_sum = 0
best_length = 0
while right < n:
    window_sum = window_sum + values[right]
    while window_sum > limit and left <= right:
        window_sum = window_sum - values[left]
        left = left + 1
    current_length = right - left + 1
    if current_length > best_length:
        best_length = current_length
    right = right + 1
print(str(best_length))

Run the full solver from this unit folder:

python assets/l2.py < assets/l2/1.in

Notice

Grow the window with a running sum; while it exceeds limit, shrink from the left; track the widest width.

Complexity: O(n) — left and right each advance at most n times.

Two-Pointer Checklist

(1) Converging pointers need a SORTED list; move the end that improves the sum; (2) a sliding window keeps a running sum and needs NON-NEGATIVE values to shrink safely; (3) longest vs shortest just flips the shrink condition; (4) each pointer moves one way → O(n).

Recap

On a sorted list, move lo up when the sum is too small and hi down when it is too big.
Each pointer moves only one way, so together they take at most n steps.
A sliding window adds values[right] as it grows and takes away values[left] as it shrinks, never re-summing.
Shrink while the window breaks the limit for the LONGEST window, or while it meets the target for the SHORTEST.
The sliding window needs non-negative values, so shrinking never raises the sum.

You can now replace slow nested-loop scans with linear two-pointer and sliding-window passes.