Two pointers, sliding window and prefix sums

Replace a nested loop with two indices that only move forward, keep a window under a constraint, and answer range queries in constant time.

Two pointers on a sorted array

from typing import Sequence

def pair_sum(xs: Sequence[int], target: int) -> tuple[int, int] | None:
    """The input must be sorted: each comparison removes one candidate."""
    lo, hi = 0, len(xs) - 1
    while lo < hi:
        s = xs[lo] + xs[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1          # the smallest value cannot be part of any answer
        else:
            hi -= 1          # the largest value cannot be part of any answer
    return None

def dedupe_sorted(xs: list[int]) -> int:
    """In-place deduplication returning the new length (the classic 26 problem)."""
    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
    return write

def container_most_water(heights: Sequence[int]) -> int:
    """Move the shorter wall inward: it is the only one that can help."""
    lo, hi = 0, len(heights) - 1
    best = 0
    while lo < hi:
        best = max(best, min(heights[lo], heights[hi]) * (hi - lo))
        if heights[lo] <= heights[hi]:
            lo += 1
        else:
            hi -= 1
    return best

def three_sum(nums: list[int]) -> list[list[int]]:
    """Sort, fix one index, then two-pointer the remainder."""
    nums.sort()
    out: list[list[int]] = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                     # skip duplicate anchors
        if nums[i] > 0:
            break                        # sorted: no later triple can sum to zero
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s == 0:
                out.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1              # skip duplicate partners
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
            elif s < 0:
                lo += 1
            else:
                hi -= 1
    return out

The key insight of the opposite-ends pattern is that each comparison eliminates one element for good. If you cannot justify that elimination, you have not found the invariant and the approach will be wrong on some input.

Fixed and variable sliding windows

from typing import Sequence

def max_sum_fixed(xs: Sequence[int], k: int) -> int:
    """A fixed window: add the entering element, subtract the leaving one."""
    if k <= 0 or k > len(xs):
        raise ValueError("k out of range")
    window = sum(xs[:k])
    best = window
    for i in range(k, len(xs)):
        window += xs[i] - xs[i - k]
        best = max(best, window)
    return best

def min_window_at_least(xs: Sequence[int], target: int) -> int:
    """The smallest window whose sum is at least target. All values positive."""
    left = 0
    running = 0
    best = len(xs) + 1
    for right, x in enumerate(xs):
        running += x
        while running >= target:          # shrink while the constraint holds
            best = min(best, right - left + 1)
            running -= xs[left]
            left += 1
    return 0 if best > len(xs) else best

def longest_window_with_distinct(s: str) -> int:
    """The variable window with a map of the last position of each character."""
    last: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1           # jump the left edge past the repeat
        last[ch] = right
        best = max(best, right - left + 1)
    return best


def character_replacement_demo(s: str, k: int) -> int:
    """Sliding window whose validity depends on a maintained histogram."""
    counts: dict[str, int] = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1
        most = max(counts.values())
        # left pointer advances when the window cannot be fixed with k changes
        if (right - left + 1) - most > k:
            counts[s[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

if __name__ == "__main__":
    print(max_sum_fixed([2, 1, 5, 1, 3, 2], 3))       # 9
    print(min_window_at_least([2, 3, 1, 2, 4, 3], 7)) # 2
    print(longest_window_with_distinct("abcabcbb"))   # 3

• Each pointer moves forward only, so the total work is O(n) even though there are two loops. The inner while amortises: it can run at most n times in total across the whole scan.
• A variable window needs a monotone condition: shrinking must never make an invalid window valid again, or the two-pointer argument breaks. Counting distinct characters is monotone; a window sum with negative values is not.
• Maintain the aggregate incrementally. Recomputing sum(xs[left:right]) each step reintroduces the O(n) inner cost.
• With a histogram, updating the maximum naively per step is O(alphabet). For a small fixed alphabet that is a constant, which is why the character-replacement solution stays linear.

Prefix sums and difference arrays

from typing import Sequence

class PrefixSum:
    """Static range-sum queries in O(1) after O(n) preprocessing."""
    __slots__ = ("_pre",)

    def __init__(self, xs: Sequence[int]) -> None:
        pre = [0] * (len(xs) + 1)
        for i, x in enumerate(xs):
            pre[i + 1] = pre[i] + x
        self._pre = pre

    def query(self, lo: int, hi: int) -> int:
        """Sum of xs[lo:hi], half open."""
        return self._pre[hi] - self._pre[lo]


def difference_array_demo(updates: list[tuple[int, int, int]], n: int) -> list[int]:
    """Apply many range additions in O(1) each, then rebuild in O(n)."""
    diff = [0] * (n + 1)
    for lo, hi, delta in updates:
        diff[lo] += delta
        diff[hi + 1] -= delta          # the effect stops after hi

    out = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        out[i] = running
    return out


def count_subarrays_sum_k(nums: Sequence[int], k: int) -> int:
    """Prefix sums plus a hash map: O(n), works with negative numbers."""
    counts: dict[int, int] = {0: 1}
    running = 0
    total = 0
    for x in nums:
        running += x
        total += counts.get(running - k, 0)
        counts[running] = counts.get(running, 0) + 1
    return total


def max_subarray_kadane(nums: Sequence[int]) -> int:
    """Not a prefix sum, but the same incremental-accumulator idea."""
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)   # restart here, or extend
        best = max(best, current)
    return best


if __name__ == "__main__":
    ps = PrefixSum([3, 1, 4, 1, 5])
    print(ps.query(1, 4))                          # 1+4+1 = 6
    print(difference_array_demo([(0, 2, 5), (1, 3, 2)], 5))  # [5, 7, 7, 2, 0]
    print(count_subarrays_sum_k([1, 1, 1], 2))     # 2
    print(max_subarray_kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6

FAQ

Related

Frequency maps, sets and hashing techniques Sorting and searching

Last refreshed 2026-09-18.