Two Pointers and Sliding Window

Two pointers replace a nested loop over pairs with two indices that only ever move forward (or toward each other). Because each pointer makes at most n moves, the whole scan is O(n). The pattern appears in many forms: closing in on a target from both ends of a sorted array, a sliding window that grows and shrinks over a string, matching one sequence inside another, and fast and slow pointers on a linked list.

Intuition

The technique is correct only when the problem has a monotone structure that lets you discard candidates for good:

• Opposite ends on sorted data. For a pair sum, if a[l] + a[r] is too large, then a[r] is too large for every remaining partner, so r can move left permanently. If the sum is too small, l moves right.
• Sliding window. If a window [l, r] satisfies a condition, every smaller window inside it does too (or every larger one does). Then for each right end r, the best left end only moves right as r grows. Expand r one step at a time, and shrink from l while the window is invalid (for "longest") or while it stays valid (for "shortest").
• Fixed window. For windows of exactly k elements, add the entering element and remove the leaving one.
• Two sequences. To test whether t is a subsequence of s, advance through s and move the pointer in t only on a match.
• Fast and slow pointers. On a linked list, a pointer moving two steps per turn catches a pointer moving one step if and only if there is a cycle.

When monotonicity fails, two pointers fail. The classic example is "subarray sum equals k" with negative numbers: growing the window can lower the sum, so neither pointer can be advanced safely. Use prefix sums with a hash map instead.

When to use it in interviews / OAs

• Sorted array plus a pair or triplet condition: two sum on sorted input, three sum, closest sum, counting pairs below a target.
• Longest or shortest contiguous subarray or substring with a condition that behaves monotonically: at most k distinct characters, no repeats, sum at least target (positive numbers), product below k, at most k zeros flipped.
• Counting subarrays: in a "longest valid window" scan, r - l + 1 windows end at r. For "exactly K", count "at most K" minus "at most K - 1".
• In-place array rewriting: remove duplicates, move zeros, partition by a predicate (a slow write pointer and a fast read pointer).
• Linked lists: cycle detection and its entry point, the middle node, the k-th node from the end.
• Merging two sorted sequences, or comparing two strings with backspaces from the end.

Template

Opposite ends: pair with a given sum

def pair_with_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    """nums is sorted. Return indices i < j with nums[i] + nums[j] == target, or None."""
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return l, r
        if s < target:
            l += 1  # nums[l] is too small for every remaining partner
        else:
            r -= 1  # nums[r] is too large for every remaining partner
    return None

Three sum without duplicate triplets

Fix the smallest element, run the pair search on the rest, and skip equal values so each triplet appears once:

def three_sum(nums: list[int]) -> list[list[int]]:
    nums = sorted(nums)
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first element as before
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                result.append([nums[i], nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1  # skip duplicate second elements
                r -= 1
    return result

Variable window: longest valid window

Longest substring without repeated characters. Grow r; when the new character repeats, shrink from l until it no longer does:

def longest_unique_substring(s: str) -> int:
    count: dict[str, int] = {}
    best = l = 0
    for r, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:  # invalid: shrink until valid again
            count[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

Variable window: shortest valid window

Minimum window of s containing every character of t (with multiplicity). Here validity survives growing, so shrink while the window is still valid and record the best:

from collections import Counter


def min_window(s: str, t: str) -> str:
    if not t:
        return ""
    need = Counter(t)
    missing = len(t)  # characters of t not yet covered by the window
    best = (0, float("inf"))
    l = 0
    for r, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:  # valid: try to shrink
            if r - l < best[1] - best[0]:
                best = (l, r)
            need[s[l]] += 1
            if need[s[l]] > 0:  # we just dropped a needed character
                missing += 1
            l += 1
    return "" if best[1] == float("inf") else s[best[0]:best[1] + 1]

Counting windows, and "exactly K" from "at most K"

With positive numbers, the product of a window only grows when it grows. For each right end, every window starting between l and r qualifies:

def count_product_less_than(nums: list[int], k: int) -> int:
    """Number of contiguous subarrays of positive integers with product < k."""
    if k <= 1:
        return 0
    product, l, total = 1, 0, 0
    for r, x in enumerate(nums):
        product *= x
        while product >= k:
            product //= nums[l]
            l += 1
        total += r - l + 1  # subarrays ending at r
    return total

"Exactly K distinct values" is not monotone, but "at most K distinct values" is:

def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
    def at_most(m: int) -> int:
        count: dict[int, int] = {}
        l = total = 0
        for r, x in enumerate(nums):
            count[x] = count.get(x, 0) + 1
            while len(count) > m:
                count[nums[l]] -= 1
                if count[nums[l]] == 0:
                    del count[nums[l]]
                l += 1
            total += r - l + 1
        return total

    return at_most(k) - at_most(k - 1)

Fast and slow pointers: where does a cycle start?

If the slow pointer has taken k steps when they meet, the fast one has taken 2k, so k is a multiple of the cycle length. A pointer restarted from the head and the slow pointer, both moving one step at a time, then meet exactly at the cycle's entry:

class ListNode:
    def __init__(self, val: int = 0):
        self.val = val
        self.next: "ListNode | None" = None


def cycle_start(head: ListNode | None) -> ListNode | None:
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:  # inside the cycle
            p = head
            while p is not slow:
                p, slow = p.next, slow.next
            return p
    return None

Testing whether t is a subsequence of s is the simplest two-sequence scan: it = iter(s); all(ch in it for ch in t).

Complexity

• Every pointer moves at most n times, so each scan is O(n) time (O(n + m) for two sequences). Sorting first adds O(n log n); three sum is O(n^2).
• Extra space: O(1) for the pointer scans, O(alphabet) or O(distinct values) for window counters.
• subarrays_with_k_distinct runs two O(n) scans.

Common pitfalls

• Using a window when the condition is not monotone, for example sums with negative numbers. Check the monotonicity argument before coding.
• Shrinking with if instead of while. One step may not restore validity.
• Updating the answer at the wrong moment: "longest" is recorded after shrinking, "shortest" is recorded inside the shrinking loop.
• Duplicate results in three sum: skip equal values for the first element and after each found triplet.
• Stale entries in the counter: delete keys whose count reaches zero when the number of distinct keys matters.
• Division with zero values in product windows; zeros need special handling (a product window assumes positive numbers).
• Fast pointer null checks: test fast and fast.next before moving two steps.

Interview variations

• Container with most water: move the shorter wall inward; the area limited by it cannot improve.
• Trapping rain water: two pointers with running left and right maxima.
• Valid palindrome (with one deletion allowed), reverse vowels, sort colors (three pointers).
• Longest repeating character replacement: window is valid while length - most_frequent_count <= k.
• Max consecutive ones III, fruit into baskets, longest substring with at most k distinct characters.
• Minimum size subarray sum (positive numbers), permutation in string and find all anagrams (fixed window of length len(p) with counts).
• Sliding window maximum: a window plus a monotonic deque.
• Remove duplicates from sorted array, move zeros, squares of a sorted array (fill from the back).
• Middle of the linked list, remove the n-th node from the end, happy number and find the duplicate number (cycle detection on an implicit sequence).