Lesson 3 of 10 · 9 min

Arrays, two pointers and sliding windows

Turn nested-loop scans into single passes when the data is sorted or the range is contiguous.

Two pointers

When an array is sorted, the sum of two elements moves predictably: advance the left pointer and the sum increases, retreat the right and it decreases. That monotonic relationship is what lets you discard half the search space with every comparison.

Without an ordering the technique is invalid, which is why the first move in problems like 3Sum is to sort.

Pair summing to a target, sorted input

def pair_sum(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:                  # < not <=, or an element pairs with itself
        total = nums[lo] + nums[hi]
        if total == target:
            return lo, hi
        if total < target:
            lo += 1                 # need a bigger number
        else:
            hi -= 1                 # need a smaller one
    return None

Sliding window

A window is a contiguous range with a constraint — longest without repeats, shortest containing all of a set, at most k distinct values. You extend the right edge, and when the constraint breaks you contract from the left.

The reason this is O(n) and not O(n²) is that each index enters the window once and leaves once. If your left pointer can ever move backwards, the pattern does not apply and you have written a quadratic loop.

Longest substring without repeating characters

def longest_unique(s):
    last = {}
    start = best = 0
    for i, ch in enumerate(s):
        # the >= start guard stops the left edge moving backwards
        if ch in last and last[ch] >= start:
            start = last[ch] + 1
        last[ch] = i
        best = max(best, i - start + 1)
    return best

Note: Drop that guard and a stale occurrence drags the window left, breaking both correctness and the complexity argument.

Prefix sums

If you need many range sums over a fixed array, precompute cumulative totals once. The sum of the range [l, r) is then prefix[r] − prefix[l], in constant time.

The same idea generalises: prefix XOR, prefix counts, prefix minimum with a little care. Whenever a problem asks about many overlapping ranges, ask whether a prefix array collapses it.

Worth remembering

Two pointers needs an ordering that makes movement decisions safe.
Sliding window needs the left edge to move only forward — that is what makes it linear.
Prefix sums answer any range-sum query in O(1) after one O(n) pass.

Test it now

The medium bank is where these two patterns are tested hardest.

Medium DSA quiz →All levels