Two Pointers & Sliding Window

You've now covered every core data structure and traversal technique in this track. The next four lessons cover patterns — reusable strategies that combine those building blocks to solve entire families of problems efficiently. We'll start with two of the most common: the two pointers technique and its close cousin, the sliding window. Both trade a naive O(n²) nested loop for a single O(n) pass by moving one or two indices through the data intelligently instead of re-scanning from scratch.

Two Pointers: The Idea

Worked Example: Two-Sum on a Sorted Array

Recall the "Two Sum" problem from the hashing lesson: given an array and a target, find two indices whose values sum to the target. The HashMap solution there ran in O(n) time and O(n) space and worked on an unsorted array. If the array is already sorted, two pointers solves it in O(n) time but only O(1) extra space — no map needed at all.

The idea: start one pointer left at index 0 and another right at the last index. If the sum of the two values is too small, the only way to increase it is to move left forward (since the array is sorted, that guarantees a larger or equal value). If the sum is too large, move right backward. The pointers converge toward each other, and every step eliminates one candidate pair for good — that's what keeps it linear.

// Array is sorted ascending. Returns the indices of the pair, or null if none exists.
public int[] twoSumSorted(int[] nums, int target) {
    int left = 0;
    int 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 null; // no pair found
}

Time complexity: O(n) — the two pointers together cover at most n steps before they meet; no element is ever revisited. Space complexity: O(1) — only two index variables, no auxiliary data structure.

Sliding Window: The Idea

Worked Example: Maximum Sum Subarray of Size K (Fixed Window)

Brute force recomputes the sum of every window of size K from scratch: O(n·K) time. A sliding window instead keeps a running sum, adding the element entering the window on the right and subtracting the element leaving it on the left, so each slide is O(1) instead of O(K).

public int maxSumSubarrayOfSizeK(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += nums[i]; // build the first window
    }

    int maxSum = windowSum;
    for (int end = k; end < nums.length; end++) {
        windowSum += nums[end] - nums[end - k]; // slide: add right, drop left
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

Time complexity: O(n) — the first window costs O(k), then every subsequent slide is O(1), for a total of O(k + (n − k)) = O(n). Space complexity: O(1) — a running sum and a max variable, nothing that grows with input size.

Worked Example: Longest Substring Without Repeating Characters (Variable Window)

This is the more advanced sliding window shape: the window's size isn't fixed — it grows while a condition holds and shrinks when it's violated. Here the condition is "no repeated characters inside the window." We track the characters currently in the window with a HashSet, expand right one character at a time, and whenever we'd introduce a duplicate, shrink from left until the duplicate is gone.

public int lengthOfLongestSubstring(String s) {
    Set<Character> windowChars = new HashSet<>();
    int left = 0;
    int maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        // shrink from the left until c is no longer a duplicate in the window
        while (windowChars.contains(c)) {
            windowChars.remove(s.charAt(left));
            left++;
        }

        windowChars.add(c);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Time complexity: O(n) — although there's a nested while loop, left only ever moves forward and never resets, so across the whole run it advances at most n times total; combined with right's n steps, the total work is O(n), not O(n²). Space complexity: O(min(n, m)) where m is the size of the character set — the HashSet holds at most one entry per distinct character currently in the window.

Recognizing Which Pattern Applies