Two Pointers and Sliding Window: Optimizing Arrays and Strings

1. Overview

When you encounter a problem traversing arrays or strings where the brute-force solution runs in O(n²) or O(n³), the two two pointers and sliding window techniques often help you reduce the complexity to O(n). This article explains the core idea of each technique, along with specific Java examples: two sum on a sorted array, palindrome checking, maximum subarray sum within a fixed window, and the longest substring without repeating characters. After reading, you’ll recognize the pattern and be able to apply it to many similar problems.

2. What is Two Pointers

Two pointers is a technique that uses two index variables (pointers) moving over a data structure (usually an array or sorted string) to avoid nested loops. The two pointers can move:

• Same direction (fast/slow): used for removing duplicate elements, detecting cycles.
• Opposite directions (left/right from both ends): used for finding pairs with a target sum, checking palindromes.

2.1. Opposite-direction Two Pointers: Finding a Pair with Target Sum

Classic problem: given a sorted array in ascending order, find two numbers whose sum equals the target.

public class TwoSumSorted {

    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{numbers[left], numbers[right]};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

Explanation:

• left starts at the beginning of the array, right from the end.
• If sum < target, the number at left is too small, so increase left to get a larger number.
• If sum > target, the number at right is too large, so decrease right.
• The loop runs at most n steps because each time left or right moves one position, giving O(n) complexity instead of O(n²) of the two-layer traversal approach.

Test with JUnit 5 + AssertJ:

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.10.2</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.25.3</version>
    <scope>test</scope>
</dependency>

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class TwoSumSortedTest {

    private final TwoSumSorted twoSum = new TwoSumSorted();

    @Test
    void shouldFindPairWhenSumMatchesTarget() {
        int[] numbers = {1, 3, 5, 8, 11};

        int[] result = twoSum.findPair(numbers, 13);

        assertThat(result).containsExactly(5, 8);
    }
}

Note: this technique requires a sorted array. If the array is not sorted, you must sort it first (O(n log n)) or use a HashMap to maintain O(n) without sorting.

2.2. Two Pointers for Palindrome Checking

public class PalindromeChecker {

    public boolean isPalindrome(String text) {
        int left = 0;
        int right = text.length() - 1;

        while (left < right) {
            if (text.charAt(left) != text.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

The two pointers start from both ends of the string, compare characters, then move toward the middle. If you find a pair of different characters, return false immediately — no need to traverse the entire string. This is why this technique is faster than reversing the string and comparing (reverse().equals()), because it avoids creating an intermediate StringBuilder object.

3. What is Sliding Window

Sliding window is a variation of two pointers, applied to problems involving contiguous subsequences (subarray/substring). Instead of recalculating from the beginning for each starting position, you maintain a “window” [left, right] and gradually update it as the window slides, reusing previously calculated results.

There are two types:

• Fixed-size window: the window size is fixed (e.g., k elements).
• Variable-size window: the size changes based on the problem condition.

3.1. Fixed-size Window: Maximum Subarray Sum of Size k

public class MaxSumSubarray {

    public int maxSum(int[] numbers, int windowSize) {
        int windowSum = 0;
        for (int i = 0; i < windowSize; i++) {
            windowSum += numbers[i];
        }

        int maxSum = windowSum;
        for (int right = windowSize; right < numbers.length; right++) {
            windowSum += numbers[right] - numbers[right - windowSize];
            maxSum = Math.max(maxSum, windowSum);
        }
        return maxSum;
    }
}

Explanation:

• The first loop calculates the sum of the first window (from index 0 to windowSize - 1).
• From there, each time you shift the window to the right by one step: add the new element (numbers[right]) and subtract the element that just left the window (numbers[right - windowSize]).
• Thanks to this, each step costs only O(1) instead of recalculating the sum O(k), so the total complexity is O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class MaxSumSubarrayTest {

    private final MaxSumSubarray solver = new MaxSumSubarray();

    @Test
    void shouldReturnMaxSumOfWindowSizeThree() {
        int[] numbers = {2, 1, 5, 1, 3, 2};

        int result = solver.maxSum(numbers, 3);

        assertThat(result).isEqualTo(9); // window [5, 1, 3]
    }
}

3.2. Variable-size Window: Longest Substring Without Repeating Characters

In this problem, the window expands and contracts based on the condition “no repeating characters”.

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public int lengthOfLongestSubstring(String text) {
        Map<Character, Integer> lastSeenIndex = new HashMap<>();
        int left = 0;
        int maxLength = 0;

        for (int right = 0; right < text.length(); right++) {
            char current = text.charAt(right);
            if (lastSeenIndex.containsKey(current) && lastSeenIndex.get(current) >= left) {
                left = lastSeenIndex.get(current) + 1;
            }
            lastSeenIndex.put(current, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Explanation:

• right always advances (expanding the window), left only jumps when encountering a duplicate character within the current window.
• lastSeenIndex stores the most recent position of each character to determine where left should jump.
• The condition lastSeenIndex.get(current) >= left ensures that a character is considered “duplicate” only if it still lies within the current window, preventing left from jumping backward incorrectly.
• Each character is processed exactly once at right, so the total complexity is O(n).

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class LongestUniqueSubstringTest {

    private final LongestUniqueSubstring solver = new LongestUniqueSubstring();

    @Test
    void shouldReturnLengthOfLongestUniqueSubstring() {
        int result = solver.lengthOfLongestSubstring("abcabcbb");

        assertThat(result).isEqualTo(3); // "abc"
    }

    @Test
    void shouldHandleAllSameCharacters() {
        int result = solver.lengthOfLongestSubstring("bbbbb");

        assertThat(result).isEqualTo(1);
    }
}

Output when manually debugging with "abcabcbb":

right=0 'a' -> window="a"    length=1
right=1 'b' -> window="ab"   length=2
right=2 'c' -> window="abc"  length=3
right=3 'a' -> duplicate, left=1 -> window="bca" length=3
right=4 'b' -> duplicate, left=2 -> window="cab" length=3
...
maxLength = 3

4. Comparison and When to Use Each Technique

Situation	Appropriate Technique
Sorted array, finding pairs/triplets satisfying sum condition	Opposite-direction two pointers
Checking symmetry (palindrome), reversing array in-place	Opposite-direction two pointers
Removing duplicate elements from a sorted array	Same-direction two pointers (fast/slow)
Subarray/substring with fixed size k	Sliding window fixed-size
Subarray/substring satisfying dynamic conditions (no repeats, sum ≤ target…)	Sliding window variable-size

Common point: both techniques avoid recalculating already processed parts, reducing from O(n²) to O(n) by maintaining state (sum, set, map) as the pointer/window moves.

5. Common Mistakes

• Forgetting the stopping condition left < right: easily causes infinite loops or comparing an element with itself when left == right.
• Applying two pointers to an unsorted array while forgetting to sort first — results are completely wrong because the pointer increment/decrement logic relies on the array’s monotonicity.
• In sliding window, forgetting to update state when left moves: for example, forgetting to remove the old element from HashMap/sum, causing the window to “remember” data that is no longer part of the window.
• Confusing the conditions for expanding/shrinking the window: with variable-size window, you must clearly determine which condition makes right advance and which makes left advance — if reversed, the window will never shrink correctly.

Note: these two techniques are not suitable when the problem requires considering all non-contiguous subsets (e.g., subset sum) — in that case, backtracking or dynamic programming is needed, not sliding window.

6. Conclusion

Two pointers and sliding window are two fundamental tools for solving array/string problems with linear complexity. Recognizing the pattern — a sorted array needing to find pairs, or consecutive subarray/substring needing optimization — helps you choose the right technique and write concise, easy-to-test code like the examples above. When practicing, try to manually draw the state of left/right at each step to clearly understand the invariant before coding.