Scrolls
5 min read
On this page

Sliding Window & Two Pointers

These two patterns show up in roughly 30% of array and string interview problems. They share a core idea: instead of brute-forcing with nested loops (O(n^2) or worse), you maintain a window or pointer pair that moves through the data in O(n). Recognizing when a problem fits one of these patterns is half the battle.

Why These Patterns Matter

Most candidates can solve "find all subarrays of size k" with brute force. The interviewer does not care about that solution. They want to see you recognize the structure of the problem and reach for the right tool. Sliding window and two pointers are the first tools you should consider when a problem involves contiguous sequences or sorted data.

Fixed-Size Sliding Window

The simplest variant. You have an array and a fixed window size k. You want to compute something (sum, max, average) for every window of size k.

The Template

function fixedWindow(arr, k):
    // compute initial window
    windowResult = compute(arr[0..k-1])
    best = windowResult

    for i from k to arr.length - 1:
        // add arr[i] to window
        // remove arr[i - k] from window
        // update windowResult
        best = max(best, windowResult)

    return best

Example: Maximum Sum Subarray of Size K

Given an array of integers and k, find the maximum sum of any contiguous subarray of size k.

arr = [2, 1, 5, 1, 3, 2], k = 3

Step 1: window = [2, 1, 5], sum = 8
Step 2: drop 2, add 1 -> window = [1, 5, 1], sum = 7
Step 3: drop 1, add 3 -> window = [5, 1, 3], sum = 9  <-- max
Step 4: drop 5, add 2 -> window = [1, 3, 2], sum = 6

Answer: 9

The key insight: you never recompute the entire sum. You subtract the element leaving the window and add the element entering. This turns O(n*k) into O(n).

Variable-Size Sliding Window

Harder and more common in interviews. The window grows and shrinks based on some condition. You expand the right boundary until a condition breaks, then shrink from the left until the condition holds again.

The Template

function variableWindow(arr):
    left = 0
    state = empty  // hashmap, counter, sum, etc.
    best = initial

    for right from 0 to arr.length - 1:
        // expand: add arr[right] to state

        while state violates condition:
            // shrink: remove arr[left] from state
            left += 1

        best = max(best, right - left + 1)  // or whatever metric

    return best

Example: Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

s = "abcabcbb"

right=0: add 'a', seen={a:0}, window="a", len=1
right=1: add 'b', seen={a:0,b:1}, window="ab", len=2
right=2: add 'c', seen={a:0,b:1,c:2}, window="abc", len=3
right=3: add 'a', duplicate! move left past previous 'a'
         left=1, seen={b:1,c:2,a:3}, window="bca", len=3
right=4: add 'b', duplicate! move left past previous 'b'
         left=2, seen={c:2,a:3,b:4}, window="cab", len=3
...

Answer: 3

The state here is a hashmap tracking the last index of each character. When you see a duplicate, jump left past the previous occurrence. This runs in O(n) because left never moves backward.

How to Recognize Variable Window Problems

Look for these phrases:

  • "Longest/shortest subarray/substring with..."
  • "Minimum window containing..."
  • "At most k distinct..."
  • "Maximum sum subarray with constraint..."

If the problem asks for a contiguous sequence that satisfies some constraint, it is almost certainly a sliding window problem.

Two Pointers on Sorted Arrays

Two pointers work when the array is sorted (or can be sorted) and you need to find pairs or triplets that satisfy a condition.

The Template

function twoPointerSorted(arr, target):
    left = 0
    right = arr.length - 1

    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        else if current < target:
            left += 1    // need a bigger sum
        else:
            right -= 1   // need a smaller sum

    return not found

This works because the array is sorted. If the sum is too small, the only way to increase it is to move the left pointer right. If the sum is too big, move the right pointer left. This guarantees you check every viable pair in O(n).

Example: Two Sum on Sorted Array

arr = [2, 7, 11, 15], target = 9

left=0, right=3: 2+15=17 > 9, right--
left=0, right=2: 2+11=13 > 9, right--
left=0, right=1: 2+7=9 == 9, return [0,1]

Three Sum

Three sum is just two sum in a loop. Sort the array, fix one element, then run two pointers on the remainder.

function threeSum(arr, target):
    sort(arr)
    for i from 0 to arr.length - 3:
        if i > 0 and arr[i] == arr[i-1]: continue  // skip duplicates
        left = i + 1
        right = arr.length - 1
        while left < right:
            sum = arr[i] + arr[left] + arr[right]
            if sum == target: record, skip duplicates, move both
            else if sum < target: left++
            else: right--

Time complexity: O(n^2), which is optimal for three sum.

Two Pointers for Palindromes

Expand from center or converge from edges. Both use two pointers moving in opposite directions.

function isPalindrome(s):
    left = 0
    right = s.length - 1
    while left < right:
        if s[left] != s[right]: return false
        left++
        right--
    return true

For "longest palindromic substring," expand from every possible center (including between-character centers for even-length palindromes). This is O(n^2) and is the expected interview solution unless Manacher's algorithm is explicitly requested (it almost never is).

Two Pointers: Container With Most Water

A classic that trips people up because the two-pointer logic is not immediately obvious.

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]

left = 0, right = 8
area = min(1, 7) * 8 = 8
Move left (it's shorter)

left = 1, right = 8
area = min(8, 7) * 7 = 49
Move right (it's shorter)

...continue until left meets right

Why move the shorter side? Because moving the taller side can never increase the area (the height is constrained by the shorter side, and the width decreases). Moving the shorter side might find a taller bar. This greedy logic makes the two-pointer approach correct.

Trapping Rain Water

This looks like a two-pointer problem but requires a different insight. The water above each position depends on the max height to its left and the max height to its right.

heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Two-pointer approach:
left = 0, right = 11
leftMax = 0, rightMax = 0

If leftMax < rightMax:
    water at left = leftMax - heights[left] (if positive)
    leftMax = max(leftMax, heights[left])
    left++
Else:
    water at right = rightMax - heights[right] (if positive)
    rightMax = max(rightMax, heights[right])
    right--

The logic: if leftMax < rightMax, we know the water at the left position is bounded by leftMax (the right side is at least as tall). This avoids the need for prefix/suffix max arrays and runs in O(n) with O(1) space.

Pattern Recognition Cheat Sheet

Problem signal                          -> Pattern
"Contiguous subarray/substring"         -> Sliding window
"Fixed size k"                          -> Fixed sliding window
"Longest/shortest with constraint"      -> Variable sliding window
"Sorted array, find pair"              -> Two pointers (converging)
"Palindrome check/find"                -> Two pointers (expanding or converging)
"Remove duplicates in-place"           -> Two pointers (fast/slow)
"Merge two sorted arrays"             -> Two pointers (parallel traversal)
"Linked list cycle detection"          -> Two pointers (fast/slow, Floyd's)

Common Pitfalls

  • Off-by-one in window size. Fixed windows: the initial window is indices 0 to k-1, not 0 to k. The loop starts at index k, not k+1.
  • Forgetting to handle duplicates. In three sum and similar problems, skipping duplicates is required to avoid duplicate results. Many candidates get the core logic right but fail this detail.
  • Moving the wrong pointer. In container with most water, moving the taller side is a common mistake. Think about why the greedy choice works before coding.
  • Resetting left incorrectly in variable windows. When you find a duplicate in "longest substring without repeats," left should jump to max(left, lastSeen[char] + 1), not just lastSeen[char] + 1. The max prevents left from moving backward.
  • Using a set when you need a map. Many sliding window problems require tracking counts or indices, not just presence. Reach for a hashmap by default.
  • Not considering empty input or single-element input. Two-pointer solutions often have edge cases when the array has 0 or 1 elements.

Key Takeaways

  • Sliding window replaces brute-force nested loops on contiguous sequences. Fixed windows are mechanical; variable windows require careful state management.
  • Two pointers on sorted arrays exploit the sort order to eliminate candidates without checking them. If the problem does not give you a sorted array, consider sorting it first.
  • These patterns are about recognition, not memorization. Learn the templates, then practice identifying which problems fit. After 15-20 problems, the pattern matching becomes instinct.
  • When stuck, ask: "Is there a way to avoid recalculating from scratch?" If yes, you probably want a window. Ask: "Can I eliminate candidates by moving a pointer?" If yes, you probably want two pointers.
  • In interviews, state the pattern name before coding. "This looks like a variable-size sliding window problem" tells the interviewer you know what you are doing.