Two pointers and sliding window

Two indexes moving through an array or string replace a nested loop: one from each end (sorted pair sums, palindromes) or one behind the other (a window of elements that grows and shrinks).

🔎 Unravel this example Prerequisites (1)

Learn these first

Arrays and the Arrays utilities

At a glance

Mental model

Measuring a stretch of a rope with two fingers: you slide the back finger forward when the stretch is too long and the front finger when it is too short, never going back.

What happens, in order

1Opposite ends: for a sorted array and a target sum, left = 0, right = n - 1; if the sum is too small move left++, if too large right--
2Same direction (slow and fast): remove duplicates in place, partition arrays, detect cycles in linked lists
3Sliding window: expand end to include new elements, shrink start while the window breaks a rule, and record the best window each stepTypical: longest substring without repeats, maximum sum of k consecutive numbers.
4Each pointer only moves forward, so the total work is at most 2n steps

Remember

First decide the invariant the window keeps ("no repeated characters", "sum at most target") and make sure the shrink step restores it
The pattern needs a property that moves monotonically: for example sorted data or only positive numbers (with negatives, a sliding window sum no longer works)
The complexity argument is amortised: although there is a loop inside a loop, the inner while moves start forward at most n times in total across the whole run

Watch out

Moving both pointers in the wrong casesOff-by-one on window size (end - start + 1)Using it on unsorted dataNot updating the window contents when shrinking

Example (highlighted lines explain it)

import java.util.*;public class Windows {  static boolean hasPairWithSum(int[] sorted, int target) {    int left = 0, right = sorted.length - 1;    while (left < right) {      int sum = sorted[left] + sorted[right];      if (sum == target) return true;      if (sum < target) left++; else right--;    }    return false;  }  static int longestUnique(String s) {    Set<Character> seen = new HashSet<>();    int start = 0, best = 0;    for (int end = 0; end < s.length(); end++) {      while (!seen.add(s.charAt(end))) seen.remove(s.charAt(start++));      best = Math.max(best, end - start + 1);    }    return best;  }}

Read the full explanation (about 1 min)

Two indexes moving through an array or string replace a nested loop: one from each end (sorted pair sums, palindromes) or one behind the other (a window of elements that grows and shrinks). It turns O(n²) into O(n).

A mental model

Measuring a stretch of a rope with two fingers: you slide the back finger forward when the stretch is too long and the front finger when it is too short, never going back.

How it works

Opposite ends: for a sorted array and a target sum, left = 0, right = n - 1; if the sum is too small move left++, if too large right--.

Same direction (slow and fast): remove duplicates in place, partition arrays, detect cycles in linked lists.

Sliding window: expand end to include new elements, shrink start while the window breaks a rule, and record the best window each step. Typical: longest substring without repeats, maximum sum of k consecutive numbers.

Each pointer only moves forward, so the total work is at most 2n steps.

Going deeper

First decide the invariant the window keeps ("no repeated characters", "sum at most target") and make sure the shrink step restores it.

The pattern needs a property that moves monotonically: for example sorted data or only positive numbers (with negatives, a sliding window sum no longer works).

Often combined with a HashMap of counts for the window contents.

Under the hood

The complexity argument is amortised: although there is a loop inside a loop, the inner while moves start forward at most n times in total across the whole run.

Common mistakes

Moving both pointers in the wrong cases.
Off-by-one on window size (end - start + 1).
Using it on unsorted data.
Not updating the window contents when shrinking.

Part of a learning path

Algorithms and data structures · previous: Sorting algorithms · next: Dynamic programming and memoisation

Related concepts

Time complexity (Big O)Java language Arrays and the Arrays utilitiesJava language Binary searchJava language

Frequently asked questions

What is Two pointers and sliding window?

What are the most common mistakes with Two pointers and sliding window?

Moving both pointers in the wrong cases. Off-by-one on window size (end - start + 1). Using it on unsorted data. Not updating the window contents when shrinking.

How can I see Two pointers and sliding window in real code?

Paste your own Java into Unravel and it will point out where two pointers and sliding window appears, explain how it works at the detail level you choose, and draw the flow of the code around it.