Unit 14 — Two Pointers & Sliding Window

Slide 1 of 28

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.
- 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

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

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

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

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
```
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

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

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

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

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
```
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).
- 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.

Unit 14 — Two Pointers & Sliding Window

Lesson 1 — Converging Two Pointers

Lesson 2 — Sliding Windows

Two-Pointer Checklist