Module 2.2 ⏱ 35 min read ⚡ Linear Data Structures

The Two-Pointer & Sliding Window Patterns

Master linear scanning optimizations by replacing nested $O(n^2)$ loops with dual indices and moving data windows to achieve sleek $O(n)$ linear efficiency.

1. Opposite-Direction Pointers

The opposite-direction pointer technique initializes two indices—typically one at the very beginning (`left = 0`) and one at the end (`right = n - 1`) of a sorted array or string. These pointers move inward toward each other based on specific evaluation conditions until they meet.

This approach is heavily utilized in problems like checking for palindromes, reversing arrays in-place, or solving the classic "Container With Most Water" problem where height constraints determine whether the left or right pointer shifts inward.

2. Fast-Slow Pointers

The fast and slow pointer pattern (also known as the Tortoise and Hare algorithm) moves two pointers through a data structure at different speeds. While the slow pointer increments by one step, the fast pointer skips ahead by two or more steps. This pattern excels at identifying cycle parameters, finding midpoints, or removing duplicates from arrays in-place.

3. Sliding Window Mechanics (Fixed vs. Variable)

The sliding window pattern replaces nested iterations by maintaining a subset of data as a "window" that moves across the array or string:

Fixed-Size Windows: The window size $k$ remains constant. As the window slides one step rightward, you drop the contribution of the outgoing element on the left and include the incoming element on the right in $O(1)$ time.

Variable-Size Windows: The window expands dynamically by moving the right boundary until a constraint is broken, then contracts by shifting the left boundary until validity is restored. This pattern powers optimization challenges like "Longest Substring Without Repeating Characters".

// C++ Solution: Longest Substring Without Repeating Characters (Variable Sliding Window)
#include <string>
#include <unordered_set>
#include <algorithm>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        std::unordered_set<char> char_set;
        int l = 0, res = 0;
        for (int r = 0; r < s.length(); ++r) {
            while (char_set.count(s[r])) {
                char_set.erase(s[l]);
                l++;
            }
            char_set.insert(s[r]);
            res = std::max(res, r - l + 1);
        }
        return res;
    }
};
            

# Python Solution: Longest Substring Without Repeating Characters (Variable Sliding Window)
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        l = 0
        res = 0
        for r in range(len(s)):
            while s[r] in char_set:
                char_set.remove(s[l])
                l += 1
            char_set.add(s[r])
            res = max(res, r - l + 1)
        return res
            

// Java Solution: Longest Substring Without Repeating Characters (Variable Sliding Window)
import java.util.HashSet;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> charSet = new HashSet<>();
        int l = 0, res = 0;
        for (int r = 0; r < s.length(); r++) {
            while (charSet.contains(s.charAt(r))) {
                charSet.remove(s.charAt(l));
                l++;
            }
            charSet.add(s.charAt(r));
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}
            

4. Homework & Quiz Overview

To lock in your mastery of this chapter, complete the implementation and dry-run exercises for our two core benchmark problems: "Container With Most Water" (Opposite-Direction Pointers) and "Longest Substring Without Repeating Characters" (Variable Sliding Window).

Quick Check: Test Your Intuition

In a variable-size sliding window algorithm (like finding the longest substring without duplicates), when do you increment the left boundary pointer (`l`)?