# Interview Patterns: Two Pointers, Sliding Windows, Prefix Sums and Monotonic Stacks — Data Structures in Python

Source: https://www.skillbyai.com/en/data-structures-python/p-patterns

> Recognise common patterns that turn O(n²) solutions into O(n).

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

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

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

- [x] Prefix sums
- [ ] Two pointers
- [ ] Monotonic stack
- [ ] Binary heap

*Answer:* Prefix sums. Range sums become a subtraction of two precomputed cumulative totals.