Two Pointers & Sliding Window

Why nested loops waste work

Consider the classic: given a sorted array, find two numbers that add up to a target. The brute force tries every pair. Element 0 with every other element, then element 1 with every other element, and so on. That is roughly n squared over two pair checks.

But most of those checks are predictable before you make them. If the array is sorted and arr[0] + arr[n-1] is already bigger than the target, then arr[0] paired with any other large element is also too big, no need to test those pairs individually. The sorted order lets one comparison eliminate a whole group of candidates at once.

That is the shared insight behind both techniques in this lesson: find a reason why, after one comparison, you can permanently discard many candidates. Discard a chunk per step, and n steps finish the job.

Converging two pointers

Place one pointer (just an index variable) at the left end and one at the right end, and move them toward each other. At each step, compare the pair they point at. In the two-sum example: if the sum is too small, only a bigger left value can help, so move left rightward. If the sum is too big, move right leftward. If it matches, done.

Why is it safe to move a pointer and never reconsider? When the sum is too small, left's current value has just failed with the largest remaining candidate. It cannot succeed with anything smaller, so it can never be part of the answer with any remaining partner. Discarding it is not a guess; it is a proof. Each step permanently retires one element, so after at most n steps the pointers meet. O(n) time, O(1) extra space.

The same converging shape solves Valid Palindrome (compare characters from both ends), Container With Most Water, and the sorted variant of 3Sum. The prerequisite is some ordering or symmetry that tells you which pointer is safe to move.

static int[] twoSumSorted(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;
        else right--;
    }
    return new int[]{-1, -1};
}

Sliding window: both pointers move the same way

A sliding window also uses two indexes, but both move left to right, and together they frame a contiguous chunk of the array. The window. The right pointer grows the window by admitting new elements; the left pointer shrinks it by evicting old ones. You maintain some running state about the window's contents, like a sum or a count map, updating it incrementally instead of rescanning.

The workhorse version is the variable-size window: grow until a rule breaks, then shrink until it holds again. Example: longest substring without repeating characters. Advance right one character at a time; if the new character is a duplicate of something in the window, advance left (evicting characters) until the duplicate is gone; record the window length whenever it is valid.

It looks like nested loops, but count the pointer movements: right moves forward at most n times, and left moves forward at most n times across the entire run. Left never goes backward. Total work is bounded by 2n, which is O(n).

static int lengthOfLongestSubstring(String s) {
    Set<Character> window = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        while (window.contains(s.charAt(right))) {
            window.remove(s.charAt(left));
            left++;
        }
        window.add(s.charAt(right));
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Choosing between them (and when neither applies)

Reach for converging two pointers when the input is sorted (or sortable) and you are hunting for a pair or triple satisfying a condition, or when you are comparing a sequence against its own reverse. The signals: sorted array, pair with target sum, palindrome.

Reach for a sliding window when the answer is a contiguous subarray or substring (longest, shortest, or count) with a rule about its contents: at most K distinct characters, sum at least S, no repeats. The word contiguous is the giveaway; if the problem allows picking scattered elements (a subsequence), a window over adjacent elements cannot represent that.

One more caution: variable-size windows rely on the rule being monotonic. Growing the window only ever pushes it toward invalid, shrinking only ever pushes it back toward valid. Negative numbers in a sum constraint break that, and you need prefix sums or other tools instead. Both techniques are really the same lesson (use problem structure to discard candidates wholesale) and that mindset carries straight into the optimization habits you will practice in the problem-solving framework lesson ahead.

Frequently asked