Interview Patterns: Two Pointers, Sliding Windows, Prefix Sums and Monotonic Stacks

Reusable problem-solving patterns

Many array and string problems are solved by a handful of patterns built on simple structures. Two pointers move from both ends (or at different speeds) through a sorted array or string: pair sums, removing duplicates in place, palindromes, merging sorted lists. Sliding window maintains a window [left, right) over a sequence, expanding and shrinking it while tracking state in a dict or Counter: longest substring without repeating characters, maximum sum of k consecutive items, smallest window containing all required items. Prefix sums precompute cumulative totals so that the sum of any range is a subtraction (prefix[j] - prefix[i]) in O(1), and combined with a dict they count subarrays with a given sum. A monotonic stack keeps elements in increasing or decreasing order to answer "next greater element" or "days until a warmer temperature" in O(n). Hash maps turn searches into lookups (two-sum), and heaps handle top-k and merging. Recognising the pattern is most of the work: when a brute-force solution has nested loops over the same data, ask which of these structures can remove the inner loop.

Four patterns in under fifty lines

Two pointers, sliding window, prefix sums with a dict, and a monotonic stack.

from collections import defaultdict
from itertools import accumulate

def pair_with_sum(sorted_prices: list[int], budget: int) -> tuple[int, int] | None:
    lo, hi = 0, len(sorted_prices) - 1                 # two pointers
    while lo < hi:
        total = sorted_prices[lo] + sorted_prices[hi]
        if total == budget:
            return sorted_prices[lo], sorted_prices[hi]
        if total < budget:
            lo += 1
        else:
            hi -= 1
    return None

def longest_unique_run(s: str) -> int:
    last_seen, left, best = {}, 0, 0                   # sliding window
    for right, ch in enumerate(s):
        if last_seen.get(ch, -1) >= left:
            left = last_seen[ch] + 1                    # shrink past the duplicate
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

def count_subarrays_with_sum(nums: list[int], target: int) -> int:
    seen = defaultdict(int, {0: 1})                    # prefix sum -> occurrences
    count = 0
    for prefix in accumulate(nums):
        count += seen[prefix - target]
        seen[prefix] += 1
    return count

def days_until_warmer(temps: list[int]) -> list[int]:
    answer, stack = [0] * len(temps), []               # stack of indices, decreasing temps
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

print(pair_with_sum([100, 250, 400, 650, 900], 1050))   # (400, 650)
print(longest_unique_run("abcabcbb"))                   # 3
print(count_subarrays_with_sum([1, 2, 3, -2, 2], 3))    # 4
print(days_until_warmer([30, 32, 31, 35, 33]))          # [1, 2, 1, 0, 0]

Explain the complexity change

In interviews, state the brute-force complexity first, then explain which structure removes the inner loop ("the dict turns the search into an O(1) lookup, so the whole solution is O(n)").

Quick check: Which pattern answers "sum of elements from i to j" in O(1) after O(n) preprocessing?

• Prefix sums
• Two pointers
• Monotonic stack
• Binary heap