Sliding Window vs Two Pointers: How to Tell Which One Fits

Sliding window and two pointers get filed together because the code looks alike: two indices, one loop, O(n). That resemblance is exactly what makes them easy to confuse under pressure. You recognise "two indices" and reach for whichever one you practised last, which may well be the wrong one.

They answer different kinds of question, and each has one precondition that, if missing, makes it silently wrong rather than slow. Knowing those two facts is the whole skill.

The problem it solves

Consider three questions that all look like "array plus two indices":

• In a sorted array, find two values that add up to 10.
• Find the length of the shortest contiguous run whose sum is at least 7.
• Find the length of the longest substring with no repeated characters.

The first is two pointers moving toward each other. The second and third are sliding windows, with both indices moving the same way. Swapping them does not produce a slower solution; it produces a wrong one, or no solution at all. The goal is to tell them apart from the problem statement, before writing code.

The intuition

Ask three questions, in order.

1. Is the answer a pair, or a contiguous range?

A pair — two values, two lines, two ends — points to converging pointers, one at each end. A range — a substring, a subarray, "consecutive" anything — points to a window whose two edges both travel left to right.

2. For a pair: is the input sorted, or can you sort it without losing what the question asks for?

Converging works by elimination. With the array sorted, if the smallest plus the largest is still too small, the smallest value cannot be in any answer — so it is dropped for good. Without order, that argument collapses. And if the question wants original indices, sorting destroys them; a hash map is the answer instead.

3. For a range: is the constraint monotonic as the window grows or shrinks?

This is the check people skip. A window only works if you can decide, from the current window alone, which edge to move — and never regret it. For "longest valid", every sub-range of a valid window must also be valid: a substring with no repeats has no repeats in any piece of it. For "shortest valid", every super-range of a valid window must also be valid: add more positive numbers and the sum can only rise.

A window is safe when growing it only ever moves validity one way. If an extra element can both help and hurt, the left edge does not know when to move.

Negative numbers break exactly this. Adding a negative value lowers the sum, so a longer window can be less valid than a shorter one inside it. The window's shrink step then throws away starts it should have kept.

Watch it run

The animation is the range case: the longest substring of abcabcbb with no repeats. The right edge only ever advances. When a character repeats, the left edge jumps past its earlier copy — and never comes back. Watch for the moment the left edge moves, and notice that it is decided entirely by what is inside the window.

That forward-only motion is what makes a window linear: each index enters once and leaves once. Converging pointers are linear for a different reason — each step retires one element from one end.

The code

The pair question and the range question side by side, then the window checked against a brute force on 3,000 random positive arrays, and broken by a two-element array with a negative number in it.

def pair_sum(nums, target):             # OPPOSITE ends: a pair, sorted input
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1                   # nums[left] can pair with nothing
        else:
            right -= 1                  # nums[right] can pair with nothing
    return None

def shortest_at_least(nums, target):    # SAME direction: a range, a window
    left, total, best = 0, 0, None
    for right, x in enumerate(nums):
        total += x                      # grow on the right
        while total >= target:          # valid: record it, then shrink the left
            width = right - left + 1
            best = width if best is None else min(best, width)
            total -= nums[left]
            left += 1
    return best

print(pair_sum([1, 3, 4, 6, 8, 11], 10))            # (2, 3)
print(shortest_at_least([2, 3, 1, 2, 4, 3], 7))     # 2

def brute(nums, target):
    widths = [j - i + 1 for i in range(len(nums)) for j in range(i, len(nums))
              if sum(nums[i:j + 1]) >= target]
    return min(widths) if widths else None

import random
random.seed(11)
cases = [([random.randint(1, 9) for _ in range(random.randint(0, 12))],
          random.randint(1, 30)) for _ in range(3000)]
print(all(shortest_at_least(a, t) == brute(a, t) for a, t in cases))   # True
print(shortest_at_least([-1, 4], 4), brute([-1, 4], 4))                # None 1

On positive numbers the window matches the brute force every time. On [-1, 4] with target 4 it finds nothing, while the answer is plainly the single element 4. The window only shrinks when it is valid; [-1, 4] sums to 3, never valid, so the useless -1 is never dropped.

When negatives are allowed, the fix is to change the question. With prefix sums, a range's sum is a difference of two prefixes, and the job becomes: for each end, find the nearest start whose prefix is low enough. A deque of candidate starts with increasing prefix values does it in one pass:

from collections import deque

def shortest_at_least_any(nums, target):   # negatives allowed
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)
    starts, best = deque(), None           # candidate starts, prefix increasing
    for j, p in enumerate(prefix):
        while starts and p - prefix[starts[0]] >= target:
            i = starts.popleft()           # shortest range starting at i found
            best = j - i if best is None else min(best, j - i)
        while starts and prefix[starts[-1]] >= p:
            starts.pop()                   # a later, lower start beats it
        starts.append(j)
    return best

mixed = [([random.randint(-5, 9) for _ in range(random.randint(0, 12))],
          random.randint(-5, 30)) for _ in range(3000)]
print(all(shortest_at_least_any(a, t) == brute(a, t) for a, t in mixed))   # True
print(shortest_at_least_any([-1, 4], 4))                                   # 1

Three thousand arrays with negatives mixed in, all matching the brute force. Background on both ingredients: prefix sums and the monotonic deque.

The complexity

• Converging pointers: O(n) time and O(1) space, plus O(n log n) if you have to sort first.
• Sliding window: O(n) time. Each index is added once and removed once, however far the left edge jumps in a single step. Space is whatever the window's state needs — a running sum is O(1), a set of characters is bounded by the alphabet.
• Prefix sums with a deque: O(n) time and O(n) space; each start enters and leaves the deque at most once.

Where it goes wrong

• A window over a non-monotonic constraint. Negative numbers, "sum exactly k", "at most k distinct" versus "exactly k distinct" — check that growing the window moves validity only one way. "Exactly k" is usually solved as "at most k" minus "at most k − 1".
• Converging on unsorted data. The loop runs and returns something. It is just not the answer.
• Sorting when the question wants original positions. Two-sum on an unsorted array wants a hash map, not sort-and-converge.
• Shrinking with if instead of while. One step of the left edge may not restore the constraint; keep shrinking until it holds.

How to say it in an interview

"First, is the answer a pair or a contiguous range? It's a range, so I'm thinking sliding window — but only if the constraint is monotonic. Here every number is positive, so extending a window can only raise its sum: once it's valid I can shrink from the left without missing anything. Each index enters and leaves once, so it's O(n). If negatives were allowed that argument fails, and I'd switch to prefix sums with a monotonic deque."

Naming the precondition before the pattern is what convinces an interviewer you chose the tool, rather than guessed it.