Two Pointers & Sliding Window

Why this pattern exists

Both patterns exist to turn an O(n²) brute-force scan — “for every starting point, look at every possible ending point” — into a single O(n) pass, by exploiting one property most brute-force solutions throw away: as one pointer moves forward, you already know something about the work the other pointer would redo. Instead of recomputing from scratch, you slide/adjust incrementally.

Recognition signals — reach for one of these when the problem says:

“sorted array” + “find a pair/triplet that sums to X” → two pointers (opposite ends)
“contiguous subarray/substring” + “longest/shortest/max/min that satisfies a condition” → sliding window
“remove duplicates in place” / “partition an array” → two pointers (same direction, read/write pointers)
“at most K distinct”, “no repeating characters”, “sum ≤ target” over a contiguous range → variable-size sliding window

Two pointers

Opposite-direction pointers (sorted input)

Two pointers start at opposite ends and move toward each other. The key invariant: because the array is sorted, moving the left pointer only increases the sum, and moving the right pointer only decreases it — so at every step there is exactly one correct move, never a need to backtrack.

Worked example: find two numbers in a sorted array that sum to 10, array [1, 3, 4, 6, 7, 9].

Step	left	right	arr[left]	arr[right]	sum	action
1	0	5	1	9	10	found

If the target were 8 instead:

Step	left	right	arr[left]	arr[right]	sum	action
1	0	5	1	9	10	sum > 8 → move right left
2	0	4	1	7	8	found

flowchart LR
    subgraph Arr["[1, 3, 4, 6, 7, 9]  target = 8"]
        A0["1"] --- A1["3"] --- A2["4"] --- A3["6"] --- A4["7"] --- A5["9"]
    end
    L["left →"] -.-> A0
    R["← right"] -.-> A5
    Note["sum=10 > 8, so right must shrink
(left can't help — array is sorted,
any larger left only increases sum)"]

Only one pointer moves per step, each element is visited at most once by each pointer → O(n) time, O(1) space, versus the brute-force O(n²) pair check.

Same-direction pointers (read/write, in-place partitioning)

A “slow” write pointer and a “fast” read pointer scan together; the fast pointer explores, the slow pointer marks where the next valid element should be written. Classic use: remove duplicates from a sorted array in place.

flowchart LR
    subgraph Arr["[1, 1, 2, 2, 3]"]
        direction LR
        B0["1"] --- B1["1"] --- B2["2"] --- B3["2"] --- B4["3"]
    end
    Slow["slow (last unique written)"] -.-> B0
    Fast["fast (scanning)"] -.-> B2
    Note2["arr[fast] != arr[slow] → slow++, write arr[fast] there"]

Java — two pointers (Two Sum II, sorted input)

public int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return new int[] { left, right };
        } else if (sum < target) {
            left++;   // need a bigger sum
        } else {
            right--;  // need a smaller sum
        }
    }
    return new int[] { -1, -1 }; // not found
}

Python — two pointers (Two Sum II, sorted input)

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        elif total < target:
            left += 1   # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return [-1, -1]  # not found

Sliding window

A window [left, right] expands by moving right forward, and contracts by moving left forward when it violates some constraint. The insight that makes this O(n) rather than O(n²): when the window slides by one position, you don’t recompute the whole window’s sum/count from scratch — you subtract the element that left and add the element that entered.

Fixed-size window (e.g., max sum of any subarray of size k)

flowchart LR
    subgraph W1["window size k=3 at pos 0: [2,1,5] sum=8"]
        direction LR
        C0["2"] --- C1["1"] --- C2["5"] --- C3["1"] --- C4["3"] --- C5["2"]
    end
    subgraph W2["slide right by 1: [1,5,1] sum = 8 - 2 + 1 = 7"]
        direction LR
        D0["2"] --- D1["1"] --- D2["5"] --- D3["1"] --- D4["3"] --- D5["2"]
    end

Each slide is O(1) work (one subtraction, one addition) instead of an O(k) resum — that’s the entire trick.

Variable-size window (e.g., longest substring without repeating characters)

Grow right to include new characters; when the constraint breaks (a duplicate appears), shrink from left until it’s satisfied again. Track the best answer as the window changes.

Worked example: "abcabcbb".

right	char	window	duplicate?	left action	window after	best len
0	a	{a}	no	—	“a”	1
1	b	{a,b}	no	—	“ab”	2
2	c	{a,b,c}	no	—	“abc”	3
3	a	{a,b,c}	yes (a)	shrink left past old ‘a‘	“bca”	3
4	b	{b,c,a}	yes (b)	shrink left past old ‘b‘	“cab”	3

sequenceDiagram
    participant L as left
    participant R as right
    participant Set as window char set

    R->>Set: add 'a' (idx0)
    R->>Set: add 'b' (idx1)
    R->>Set: add 'c' (idx2)
    R->>Set: try add 'a' (idx3) — duplicate!
    L->>Set: remove chars until 'a' (old idx0) is gone
    Set-->>R: 'a' (idx3) now addable
    Note over L,R: window shrinks from the left only as far as needed,<br/>never resets to empty — this is what keeps it O(n) not O(n²)

Java — sliding window (longest substring without repeating characters)

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;   // jump left past the duplicate
        }
        lastSeen.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Python — sliding window (longest substring without repeating characters)

def length_of_longest_substring(s: str) -> int:
    last_seen: dict[str, int] = {}
    left = best = 0
    for right, c in enumerate(s):
        if c in last_seen and last_seen[c] >= left:
            left = last_seen[c] + 1   # jump left past the duplicate
        last_seen[c] = right
        best = max(best, right - left + 1)
    return best

Note the left jump: rather than shrinking one character at a time until the duplicate is gone, jumping directly to last_seen[c] + 1 is an O(1) amortized optimization — left still only ever moves forward, so total movement across the whole run is still bounded by n, just done in fewer, bigger steps.

Complexity comparison

Approach	Time	Space	Why
Brute force (nested loop over all subarrays/pairs)	O(n²) or O(n³)	O(1)	Recomputes overlapping work at every start index
Two pointers (sorted input)	O(n)	O(1)	Each pointer moves at most n times total, never backtracks
Sliding window (fixed size k)	O(n)	O(1)	O(1) update per slide instead of O(k) resum
Sliding window (variable size)	O(n) amortized	O(k) (window contents)	`left` and `right` each traverse the array at most once total

Common pitfalls

Two pointers on unsorted input: the “move left if sum too small” logic only works because the array is sorted — on unsorted input there’s no guaranteed direction to move, and the pattern silently gives wrong answers instead of erroring. Sort first (O(n log n)) if the problem doesn’t guarantee sorted input, or use a hash-map approach instead if sorting would destroy needed index information.
Off-by-one on window bounds: window length is right - left + 1, not right - left — a common source of answers that are off by exactly one.
Forgetting to shrink fully: in variable-window problems, shrinking by only one step per outer iteration instead of while (constraint violated) can leave the window in an invalid state and undercount.
Recomputing the window’s aggregate from scratch on every slide: this silently degrades a fixed-size window solution back to O(nk) — the whole point is the O(1) incremental update (subtract outgoing, add incoming).

Practice problems

Two Sum II — Input Array Is Sorted (opposite-direction two pointers)
Container With Most Water (opposite-direction two pointers, greedy shrink of the shorter side)
3Sum (fix one element, two pointers on the rest)
Longest Substring Without Repeating Characters (variable sliding window)
Minimum Window Substring (variable sliding window, hardest of the set — shrink condition depends on a multi-character count map, not a single duplicate check)
Sliding Window Maximum (fixed window + monotonic deque to get the max in O(1) amortized per slide, not O(k))
Remove Duplicates from Sorted Array (same-direction read/write pointers)

Interview angles

“Why is this O(n) and not O(n²)?” — be ready to state the invariant precisely: each pointer only ever moves forward (or toward the other pointer), so total pointer movement across the whole algorithm is bounded by 2n, not n per outer iteration.
“The array isn’t sorted — does two pointers still work?” — no; name the fix (sort first, if index/order isn’t otherwise needed, or switch to a hash-map-based approach).
“Minimum Window Substring is a step up from Longest Substring Without Repeats — why?” — the shrink condition becomes “does my current window still contain all required characters at required counts,” which needs a frequency map and a “how many required characters are currently satisfied” counter, not just a single boolean duplicate check.
“How would you get the window maximum without rescanning the whole window each time?” — monotonic deque: keep indices in the window whose values are in decreasing order, popping from the back whenever a new larger element arrives (they can never be the max while the new element is in the window) and from the front once the max falls out of the window’s left bound.

Notes

Explorer