# Two Pointers & the Sliding Window

> Two array patterns that turn nested-loop O(n²) scans into single-pass O(n) code: converging two pointers on a sorted array, the fixed and variable sliding window, and how to spot which one a problem is quietly asking for.


---

# Two Pointers & the Sliding Window

A huge number of array and string problems have an obvious solution that checks every pair with two
nested loops - and that solution is `O(n²)`, which quietly falls over the moment the input gets big. Two
patterns rescue most of those problems and bring them down to a single pass, `O(n)`: the **two-pointer**
technique and the **sliding window**. They look like tricks the first time you see them, but they're really
one idea - *keep a couple of positions moving through the array so you never re-scan what you've already
seen.*

Every example here is Python you can run as you read. Once the shape clicks, you'll start recognizing it in
problems that never mention "pointers" or "windows" at all.

## How to read this

Read in order. Two pointers comes first because it's the simpler motion (two positions walking toward each
other); the sliding window is the same instinct applied to a moving range. The last phase is the payoff:
how to look at a fresh problem and tell which pattern it wants.

## The phases

1. **[Converging Two Pointers](01-converging-two-pointers.md)** · 🟢 Basic - two positions walking inward:
   reverse a list, check a palindrome, and find a pair that sums to a target on a sorted array.
2. **[The Sliding Window](02-the-sliding-window.md)** · 🟡 Intermediate - a moving range over the data: max
   sum of `k` consecutive items, and the longest substring with no repeated character.
3. **[Choosing the Pattern](03-choosing-the-pattern.md)** · 🟢 Basic - the signals that tell you which
   pattern a problem wants, and the gotchas (unsorted input, off-by-one bounds) that bite everyone once.


---

# Converging Two Pointers

The first two-pointer motion to learn is the simplest: put one pointer at the **start** of the array and
one at the **end**, then walk them toward each other. Each step you look at the pair they point to, make a
decision, and move one (or both) pointers inward. When they meet, you're done. That's a single pass over the
data - `O(n)` time - and it uses no extra memory beyond the two index variables.

## Warm-up: reverse a list in place

The cleanest way to feel the motion is reversing a list. Swap the two ends, step inward, repeat until the
pointers meet in the middle.

```python runnable
def reverse_in_place(items):
    lo, hi = 0, len(items) - 1
    while lo < hi:
        items[lo], items[hi] = items[hi], items[lo]
        lo += 1
        hi -= 1
    return items

print(reverse_in_place([1, 2, 3, 4, 5]))
```
```console
[5, 4, 3, 2, 1]
```
*What just happened:* `lo` starts at the front, `hi` at the back. Each loop swaps those two elements and
then steps both pointers one place toward the center. The loop condition `lo < hi` stops them the instant
they cross (or land on the same middle element, which needs no swap). Nothing is ever visited twice.

📝 **Terminology.** People say "two pointers," but in Python these are just **integer indices**. The word
"pointer" is borrowed from lower-level languages; here it only means "a position we move through the array."

## Palindrome check: same motion, different decision

A palindrome reads the same forward and backward - so compare the two ends, and if they ever disagree, it
isn't one. Otherwise step inward and keep checking.

```python runnable
def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        if s[lo] != s[hi]:
            return False
        lo += 1
        hi -= 1
    return True

print(is_palindrome("racecar"))
print(is_palindrome("hello"))
```
```console
True
False
```
*What just happened:* the pointers start at both ends and compare. `"racecar"` matches at every step until
they meet, so it returns `True`. `"hello"` fails immediately - `h` at the front doesn't match `o` at the
back - so it returns `False` without bothering to check the rest.

## The real one: pair with a target sum (sorted array)

Here's where converging pointers earn their keep. Given a **sorted** array, find two elements that add up
to a target. The naive approach checks every pair with two nested loops - `O(n²)`. But because the array is
sorted, the two ends tell you exactly which way to move:

- If the current pair sums to **too little**, the only way to get a bigger sum is to move the **low** pointer
  right (toward larger values).
- If it sums to **too much**, move the **high** pointer left (toward smaller values).
- If it's exactly the target, you're done.

```python runnable
def has_pair_with_sum(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        current = nums[lo] + nums[hi]
        if current == target:
            return (lo, hi)
        elif current < target:
            lo += 1
        else:
            hi -= 1
    return None

print(has_pair_with_sum([1, 3, 4, 5, 7, 11], 9))
print(has_pair_with_sum([1, 3, 4, 5, 7, 11], 100))
```
```console
(2, 3)
None
```
*What just happened:* for target `9`, the pointers start at `1` and `11` (sum `12`, too big → `hi` moves
left), then `1` and `7` (sum `8`, too small → `lo` moves right), then `3` and `7` (`10`, too big → `hi`
left), then `4` and `5` (`9`, match → return indices `(2, 3)`). Target `100` can never be reached; the
pointers cross and the function returns `None`. One pass, no nested loop.

💡 **Key point.** This shortcut *only works because the array is sorted.* Sorted order is what makes "too
small → move right, too big → move left" a reliable decision. On an unsorted array this logic silently
gives wrong answers - a trap we'll return to in Phase 3.

## The same pair-sum, in other languages

The motion is identical in every language: an index at each end, a decision, one pointer steps inward. The
typed languages just spell out the array and integer types, and each returns "not found" in its own idiom.

[[codegroup Pair With Target Sum]]

```python
def has_pair_with_sum(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        current = nums[lo] + nums[hi]
        if current == target:
            return (lo, hi)
        elif current < target:
            lo += 1
        else:
            hi -= 1
    return None
```

```javascript
function hasPairWithSum(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const current = nums[lo] + nums[hi];
    if (current === target) return [lo, hi];
    if (current < target) lo++;
    else hi--;
  }
  return null;
}
```

```typescript
function hasPairWithSum(nums: number[], target: number): [number, number] | null {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const current = nums[lo] + nums[hi];
    if (current === target) return [lo, hi];
    if (current < target) lo++;
    else hi--;
  }
  return null;
}
```

```java
static int[] hasPairWithSum(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int current = nums[lo] + nums[hi];
        if (current == target) return new int[]{lo, hi};
        if (current < target) lo++;
        else hi--;
    }
    return null;
}
```

```cpp
// returns {-1, -1} when no pair is found
std::pair<int, int> has_pair_with_sum(const std::vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int current = nums[lo] + nums[hi];
        if (current == target) return {lo, hi};
        if (current < target) lo++;
        else hi--;
    }
    return {-1, -1};
}
```

```go
func hasPairWithSum(nums []int, target int) (int, int, bool) {
    lo, hi := 0, len(nums)-1
    for lo < hi {
        current := nums[lo] + nums[hi]
        if current == target {
            return lo, hi, true
        } else if current < target {
            lo++
        } else {
            hi--
        }
    }
    return 0, 0, false
}
```

```rust
fn has_pair_with_sum(nums: &[i32], target: i32) -> Option<(usize, usize)> {
    if nums.is_empty() {
        return None;
    }
    let (mut lo, mut hi) = (0usize, nums.len() - 1);
    while lo < hi {
        let current = nums[lo] + nums[hi];
        if current == target {
            return Some((lo, hi));
        } else if current < target {
            lo += 1;
        } else {
            hi -= 1;
        }
    }
    None
}
```

[[/codegroup]]

Notice the loop condition is `lo < hi`, not `lo <= hi`. Pairing an element *with itself* isn't a valid pair,
so the pointers must stay strictly apart. That single character is a real bug source - the next phase's
cousin (the sliding window) has its own version of the same off-by-one hazard.

```quiz
[
  {
    "q": "In the pair-sum function, why does moving `lo` right when the sum is too small work?",
    "choices": ["Because the array is sorted, so larger values are to the right", "Because it's faster to increment than decrement", "Because the target is always positive", "It doesn't matter which pointer moves"],
    "answer": 0,
    "explain": "Sorted order guarantees values increase to the right. A sum that's too small can only grow by moving the low pointer toward the larger values."
  },
  {
    "q": "Why does the converging loop use `while lo < hi` instead of `while lo <= hi`?",
    "choices": ["To run one extra iteration for safety", "So an element is never paired with itself, and the pointers stop when they meet", "Because `<=` is slower", "To handle empty arrays only"],
    "answer": 1,
    "explain": "A valid pair needs two distinct positions. `lo < hi` keeps them strictly apart and stops the loop the moment they meet or cross."
  }
]
```


---

# The Sliding Window

The sliding window is the same instinct as two pointers - move positions through the array instead of
re-scanning - applied to a **range** rather than a pair. You keep a "window" covering some slice of the
data, and as it slides forward you *update* a running result cheaply instead of recomputing it from
scratch. That difference, update vs recompute, is exactly what turns an `O(n·k)` or `O(n²)` brute force into
a single `O(n)` pass.

There are two flavors: a **fixed** window that stays a constant width, and a **variable** window that grows
and shrinks based on a condition. We'll do one of each.

## Fixed window: max sum of k consecutive items

Given a list of numbers, find the largest sum of any `k` items in a row. The brute-force version re-adds `k`
numbers for every starting position - `O(n·k)`. The window trick: compute the first window's sum once, then
each time you slide one step right, **add the entering number and subtract the leaving one.** That's two
operations per step, no matter how big `k` is.

```python runnable
def max_sum_of_k(nums, k):
    window = sum(nums[:k])        # sum of the first window, computed once
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # add the new item, drop the old one
        best = max(best, window)
    return best

print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3))
```
```console
9
```
*What just happened:* the first window `[2, 1, 5]` sums to `8`. Sliding right, we add `nums[3] = 1` and drop
`nums[0] = 2`, giving `7` for `[1, 5, 1]`. Next add `3`, drop `1` → `9` for `[5, 1, 3]`. Next add `2`, drop
`5` → `6` for `[1, 3, 2]`. The best seen is `9`. Each slide did one addition and one subtraction - never a
fresh re-sum of the whole window.

💡 **Key point.** The whole savings comes from `window += nums[i] - nums[i - k]`. The value leaving the
window on the left is `nums[i - k]` - exactly `k` positions behind the value entering on the right. Get that
index wrong and every sum after the first is garbage.

## Variable window: longest substring without repeats

Now a window that *changes size*. Given a string, find the length of the longest run with no repeated
character. Grow the window to the right one character at a time; when the new character would create a
duplicate, jump the left edge forward past the previous copy so the window is valid again. Track the widest
valid window you ever see.

```python runnable
def longest_unique(s):
    seen = {}          # character -> its most recent index
    start = 0          # left edge of the current window
    best = 0
    for i, ch in enumerate(s):
        if ch in seen and seen[ch] >= start:
            start = seen[ch] + 1      # jump past the earlier copy
        seen[ch] = i
        best = max(best, i - start + 1)
    return best

print(longest_unique("abcabcbb"))
print(longest_unique("bbbbb"))
print(longest_unique("pwwkew"))
```
```console
3
1
3
```
*What just happened:* `i` is the right edge; `start` is the left edge. For `"abcabcbb"`, the window grows to
`"abc"` (length 3), then the second `a` forces `start` past the first `a`, and from then on no window beats
length 3. `"bbbbb"` can never hold more than a single `b`, so the answer is 1. `"pwwkew"` peaks at `"wke"`
(or `"kew"`), length 3. The `seen[ch] >= start` check matters: it only jumps the left edge when the repeat
is *inside the current window*, ignoring stale copies that already fell off the left.

⚠️ **Gotcha.** The dictionary here stores each character's *most recent* index, and we only shrink the
window when the repeat sits at or after `start`. Skip that `>= start` guard and an old, already-discarded
duplicate will yank `start` backward, producing windows that are too long and wrong answers on strings like
`"abba"`.

## Why this is O(n)

In both functions each element is entered by the right edge exactly once, and (in the variable case) left
behind by the `start` edge at most once. Neither pointer ever moves backward. Two forward-only pointers over
`n` elements is `O(n)` total work - even though the variable window has a nested-looking "shrink" step, no
element is processed more than a constant number of times.

```quiz
[
  {
    "q": "In the fixed-window max-sum, what does `window += nums[i] - nums[i - k]` accomplish?",
    "choices": ["Recomputes the whole window from scratch", "Adds the entering element and subtracts the one leaving the window", "Doubles the window size", "Removes duplicates from the window"],
    "answer": 1,
    "explain": "Sliding one step right means one new element enters and one old element (k positions back) leaves. Updating by that difference avoids re-summing the window each step."
  },
  {
    "q": "Why is the sliding window O(n) rather than O(n²), even the variable-size one?",
    "choices": ["It uses recursion", "Both the right edge and the left edge only ever move forward, so each element is handled a constant number of times", "It sorts the input first", "k is always small"],
    "answer": 1,
    "explain": "Neither edge moves backward. Across the whole run each element is entered once and left once, which is linear total work."
  }
]
```


---

# Choosing the Pattern

You've seen both motions. The hard part in practice isn't writing them - it's looking at a brand-new problem
and realizing *"oh, this is a two-pointer problem"* before you waste time on a nested loop. This phase is
about the signals, and about the mistakes that make a correct-looking solution quietly wrong.

## The signals

**Reach for converging two pointers when:**

- The input is **sorted** (or you're allowed to sort it first), and
- You're looking at the **relationship between two ends** - a pair that sums to something, the closest pair,
  or squeezing inward (reverse, palindrome).

**Reach for a sliding window when:**

- You want the best (longest, shortest, max-sum) **contiguous** run - a subarray or substring, and
- The window has a clear rule for when to **grow** (keep taking) and when to **shrink** (a constraint broke,
  like a repeat or a sum going over a limit).

The word "contiguous" is the loudest hint for a window: subarrays and substrings are contiguous, so a
question about the best run of adjacent elements is almost always a window. If the problem instead lets you
pick elements from anywhere and the data is sorted, it's usually converging pointers.

⚠️ **Gotcha.** A window only works when growing the range moves the result in one predictable direction
(longer window → bigger sum, for non-negative numbers). If the array has **negative numbers**, "max sum of
any subarray" is *not* a plain sliding-window problem - a longer window can lower the sum, so the shrink
rule breaks down. (That specific problem has its own classic answer, Kadane's algorithm.)

## Gotcha 1: two-pointer pair-sum needs sorted input

This is the mistake everyone makes once. The pair-sum logic from Phase 1 leans entirely on sorted order.
Feed it an unsorted array and it happily returns the wrong answer - no error, just a lie.

```python runnable
def has_pair_with_sum(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        current = nums[lo] + nums[hi]
        if current == target:
            return (lo, hi)
        elif current < target:
            lo += 1
        else:
            hi -= 1
    return None

# 5 + 4 = 9 clearly exists here, but the list is NOT sorted:
print(has_pair_with_sum([5, 1, 4, 3], 9))
```
```console
None
```
*What just happened:* the pair `5 + 4 = 9` is right there, but the algorithm never finds it. Starting at
`5` and `3` (sum `8`, too small), it moves `lo` right - past the `5` it needed - and the pointers cross
before the real pair is ever considered. The fix is to sort first (`nums = sorted(nums)`), remembering that
sorting changes the indices, so if you need *original* positions, pair each value with its index before
sorting or switch to the hash-map approach from the [Hashing for Speed](/guides/hashing-for-speed) guide.

## Gotcha 2: the loop bound (`<` vs `<=`)

Converging pointers almost always want `while lo < hi`. Using `<=` lets the two pointers land on the *same*
index, which for pair-sum means adding an element to itself - inventing a pair that doesn't exist.

```python runnable
def buggy_pair(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                 # bug: should be <
        if nums[lo] + nums[hi] == target:
            return (lo, hi)
        elif nums[lo] + nums[hi] < target:
            lo += 1
        else:
            hi -= 1
    return None

# No two distinct elements here sum to 8, so the real answer is "no pair"... but:
print(buggy_pair([1, 4, 6], 8))
```
```console
(1, 1)
```
*What just happened:* with `<=`, the pointers both settle on index `1` (value `4`), and `4 + 4 = 8` matches
the target - so it reports the "pair" `(1, 1)`. But that's one element counted twice, not two elements. The
strict `lo < hi` from Phase 1 never allows the pointers to land on the same index, so it correctly returns
`None` here.

## Gotcha 3: forgetting to shrink the window

A sliding window that only ever *grows* isn't a window - it's just a running total over the whole array. The
shrink step (moving the left edge, or subtracting the leaving element) is what keeps the window valid. Leave
it out of the "longest substring without repeats" and the window keeps a duplicate inside it, over-counting
the length. If your window answer is always suspiciously close to the full input size, a missing shrink is
the first thing to check.

💡 **Key point.** Both patterns share one promise: **every pointer moves forward only.** The moment you find
yourself wanting to move a pointer *backward* to recheck something, that's the signal you've picked the
wrong pattern (or need an auxiliary structure like a hash map) - not that you should add a backward step.

```quiz
[
  {
    "q": "A problem asks for the longest contiguous substring meeting some condition. Which pattern fits best?",
    "choices": ["Converging two pointers", "A sliding window", "Binary search", "Neither - it needs nested loops"],
    "answer": 1,
    "explain": "\"Longest contiguous run meeting a condition\" is the classic sliding-window signature: grow while the condition holds, shrink when it breaks."
  },
  {
    "q": "You run the Phase 1 pair-sum function on an unsorted array and it returns None even though a valid pair exists. What's wrong?",
    "choices": ["The target is too large", "The two-pointer pair-sum logic requires sorted input", "You should use `<=` instead of `<`", "The array is too small"],
    "answer": 1,
    "explain": "The \"too small → move right, too big → move left\" decision only holds when values are sorted. On unsorted data it skips past the answer."
  },
  {
    "q": "What single property do both the two-pointer and sliding-window patterns rely on for their O(n) speed?",
    "choices": ["The input is always numeric", "Every pointer only ever moves forward, so no element is reprocessed many times", "They both sort the data first", "They use recursion instead of loops"],
    "answer": 1,
    "explain": "Forward-only pointers mean each element is handled a constant number of times, which is what makes the whole pass linear."
  }
]
```