Two Pointers & Sliding Window

Why These Two Patterns Together?

Both patterns answer the same fundamental question: "How do I avoid checking every possible pair/subarray?"

• Two Pointers exploits sorted order or structural constraints to prune the search space.
• Sliding Window exploits contiguous subarray/substring structure to maintain state incrementally.

The key insight: if your brute force is two nested loops over indices i and j, and there is a monotonic relationship between them, you can often reduce to a single pass.

Two Pointers

Core Concept

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
graph LR
    subgraph "Sorted Array: [1, 3, 5, 7, 9, 11, 15]"
        direction LR
        A["1"] --- B["3"] --- C["5"] --- D["7"] --- E["9"] --- F["11"] --- G["15"]
    end
    L["L pointer →"] -.-> A
    R["← R pointer"] -.-> G

    style L fill:#DCFCE7,stroke:#16A34A,color:#14532D
    style R fill:#FEE2E2,stroke:#DC2626,color:#7F1D1D

Two pointers work when you can make a binary decision at each step: move the left pointer right, or move the right pointer left. This decision must be justified by a monotonic property (e.g., "the sum is too small, so moving left inward cannot help").

Three Variants

Variant A: Opposite Ends Converging

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph Step1["Step 1: L=0, R=6"]
        direction LR
        a1["[1"] --- a2["3"] --- a3["5"] --- a4["7"] --- a5["9"] --- a6["11"] --- a7["15]"]
    end
    subgraph Step2["Step 2: L=1, R=6"]
        direction LR
        b1["1"] --- b2["[3"] --- b3["5"] --- b4["7"] --- b5["9"] --- b6["11"] --- b7["15]"]
    end
    subgraph Step3["Step 3: L=1, R=5"]
        direction LR
        c1["1"] --- c2["[3"] --- c3["5"] --- c4["7"] --- c5["9"] --- c6["11]"] --- c7["15"]
    end
    Step1 --> Step2
    Step2 --> Step3

Use when: Sorted array, looking for pairs that satisfy a condition (target sum, max area, palindrome check).

Template:

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

    while (left < right) {
        int current = evaluate(arr, left, right);

        if (current == target) {
            return result; // or record and continue
        } else if (current < target) {
            left++;  // need bigger value
        } else {
            right--; // need smaller value
        }
    }
    return -1; // not found
}

Variant B: Same Direction — Fast/Slow

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph "Linked List / Array"
        direction LR
        n1["1"] --> n2["2"] --> n3["3"] --> n4["4"] --> n5["5"] --> n6["6"]
    end
    S["Slow (1 step)"] -.-> n1
    F["Fast (2 steps)"] -.-> n1

    style S fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style F fill:#FEF3C7,stroke:#D97706,color:#78350F

Use when: Cycle detection (Floyd's), finding middle, removing N-th from end, in-place array dedup.

Template:

public ListNode fastSlow(ListNode head) {
    ListNode slow = head, fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;        // 1 step
        fast = fast.next.next;   // 2 steps

        if (slow == fast) {
            return slow; // cycle detected
        }
    }
    return slow; // middle of list (no cycle)
}

Variant C: Fixed Gap

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph "Array with gap = 3"
        direction LR
        d1["a0"] --- d2["a1"] --- d3["a2"] --- d4["a3"] --- d5["a4"] --- d6["a5"]
    end
    P1["P1"] -.-> d1
    P2["P2 (gap=3)"] -.-> d4

    style P1 fill:#DCFCE7,stroke:#16A34A,color:#14532D
    style P2 fill:#FEE2E2,stroke:#DC2626,color:#7F1D1D

Use when: Finding the N-th node from end, checking if a distance-K pair exists, comparing elements with fixed separation.

Template:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode first = dummy, second = dummy;

    // Advance first pointer by n+1 steps
    for (int i = 0; i <= n; i++) {
        first = first.next;
    }

    // Move both until first hits end
    while (first != null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next; // skip the target
    return dummy.next;
}

Pattern Recognition Table

Sliding Window

Core Concept

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph "Array: [2, 1, 5, 1, 3, 2]"
        direction LR
        e1["2"] --- e2["1"] --- e3["5"] --- e4["1"] --- e5["3"] --- e6["2"]
    end

    subgraph "Window expands →"
        direction LR
        W["left=0, right=2, state=sum(8)"]
    end

    style W fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F

The window represents the current candidate subarray/substring. The algorithm has two phases that interleave:

1. Expand (move right forward) — explore new possibilities
2. Shrink (move left forward) — restore validity or optimize

Three Types

Type 1: Fixed-Size Window

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph "Window of size K=3 slides across"
        direction LR
        f1["[2, 1, 5]"] -->|"slide"| f2["[1, 5, 1]"] -->|"slide"| f3["[5, 1, 3]"] -->|"slide"| f4["[1, 3, 2]"]
    end

Use when: "Maximum/minimum sum of subarray of size K", "average of subarrays of size K".

Template:

public int fixedWindow(int[] arr, int k) {
    int windowSum = 0, maxSum = Integer.MIN_VALUE;

    for (int right = 0; right < arr.length; right++) {
        windowSum += arr[right]; // expand

        if (right >= k - 1) {
            maxSum = Math.max(maxSum, windowSum);
            windowSum -= arr[right - k + 1]; // shrink (remove leftmost)
        }
    }
    return maxSum;
}

Type 2: Variable Window — Find Longest Valid

Goal: Find the longest subarray/substring that satisfies a constraint.

Strategy: Expand greedily. Shrink only when the window becomes invalid.

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart TD
    A["Initialize left=0, right=0, windowState"] --> B["Expand: add arr[right] to state"]
    B --> C{"Is window valid?"}
    C -->|"Yes"| D["Update maxLength = max(maxLength, right-left+1)"]
    C -->|"No"| E["Shrink: remove arr[left] from state, left++"]
    E --> C
    D --> F["right++"]
    F --> B

Template:

public int longestValid(String s) {
    Map<Character, Integer> windowState = new HashMap<>();
    int left = 0, maxLength = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        windowState.merge(c, 1, Integer::sum); // expand

        while (!isValid(windowState)) {         // shrink until valid
            char leftChar = s.charAt(left);
            windowState.merge(leftChar, -1, Integer::sum);
            if (windowState.get(leftChar) == 0) {
                windowState.remove(leftChar);
            }
            left++;
        }

        maxLength = Math.max(maxLength, right - left + 1); // record
    }
    return maxLength;
}

Type 3: Variable Window — Find Shortest Valid

Goal: Find the shortest subarray that satisfies a constraint.

Strategy: Expand until valid. Then shrink as much as possible while still valid, recording the minimum at each valid state.

Template:

public int shortestValid(int[] arr, int target) {
    int left = 0, windowSum = 0;
    int minLength = Integer.MAX_VALUE;

    for (int right = 0; right < arr.length; right++) {
        windowSum += arr[right]; // expand

        while (windowSum >= target) {             // valid! try to shrink
            minLength = Math.min(minLength, right - left + 1);
            windowSum -= arr[left];
            left++;
        }
    }
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

Solved Walkthroughs

Problem 1: Container With Most Water (LC #11) — Two Pointers

Brute Force: Check every pair (i, j) — O(n^2).

The Insight: Start with the widest container (left=0, right=n-1). Area = min(height[L], height[R]) * (R - L). When you move a pointer inward, width decreases by 1. The ONLY way area can increase is if height increases. So move the pointer with the shorter height — keeping the taller one cannot help because min() is already bottlenecked by the shorter side.

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxWater = 0;

    while (left < right) {
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxWater = Math.max(maxWater, width * h);

        // Move the shorter side inward
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxWater;
}

Complexity: O(n) time, O(1) space.

Common Mistakes:

• Moving the taller pointer instead of the shorter one (destroys the greedy guarantee)
• Forgetting that when heights are equal, moving either works (but you must move at least one)

Problem 2: 3Sum (LC #15) — Two Pointers

Brute Force: Three nested loops — O(n^3).

The Insight: Sort the array. Fix one element nums[i], then the problem reduces to "Two Sum II" on the remaining sorted subarray — use opposite-end two pointers to find pairs summing to -nums[i].

The Dedup Trick: After sorting, skip consecutive duplicates at three levels:

1. Skip duplicate i values (outer loop)
2. After finding a valid triplet, skip duplicate left values
3. After finding a valid triplet, skip duplicate right values

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums); // O(n log n)

    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicate i values
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        // Early termination: if smallest element > 0, no solution possible
        if (nums[i] > 0) break;

        int left = i + 1, right = nums.length - 1;
        int target = -nums[i];

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // Skip duplicates for left and right
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;

                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

Complexity: O(n^2) time (sort + n iterations of two-pointer), O(1) extra space (ignoring output).

Common Mistakes:

• Forgetting to sort first — two pointers require sorted order
• Deduplicating at only one level (you need all three)
• Using nums[left] == nums[left - 1] instead of nums[left] == nums[left + 1] after finding a result (off-by-one in dedup direction)
• Not handling the early termination when nums[i] > 0

Problem 3: Longest Substring Without Repeating Characters (LC #3) — Sliding Window

Brute Force: Check every substring, verify no duplicates — O(n^3) with HashSet per window, or O(n^2) with optimization.

The Insight: This is "Variable Window — Find Longest Valid". The validity condition is "no character appears more than once in the window." Use a HashMap to store the last seen index of each character. When you encounter a repeat, jump left directly to lastSeen + 1 instead of sliding one by one.

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

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

        // If char was seen and is within current window, jump left
        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;
        }

        lastSeen.put(c, right); // update last seen position
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

Complexity: O(n) time, O(min(n, alphabet_size)) space.

Common Mistakes:

• Not checking lastSeen.get(c) >= left — the character might have been seen before the current window started (stale entry)
• Using a frequency map with a while-loop shrink (works but more complex for this problem)
• Confusing this with the "at most K distinct characters" variant (different validity condition)

Problem 4: Minimum Window Substring (LC #76) — Sliding Window

Brute Force: Check every substring of s, verify it contains all of t — O(n^2 * m).

The Insight: This is "Variable Window — Find Shortest Valid." The validity condition: the window contains all characters of t with required frequencies. The optimization: instead of comparing full frequency maps each time, maintain a formed counter that tracks how many unique characters have met their required count.

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";

    // Build required frequency map
    Map<Character, Integer> required = new HashMap<>();
    for (char c : t.toCharArray()) {
        required.merge(c, 1, Integer::sum);
    }

    int requiredSize = required.size(); // unique chars needed
    int formed = 0;                     // unique chars with count met

    Map<Character, Integer> windowCounts = new HashMap<>();
    int left = 0;
    int minLen = Integer.MAX_VALUE;
    int minLeft = 0;

    for (int right = 0; right < s.length(); right++) {
        // Expand: add s[right] to window
        char c = s.charAt(right);
        windowCounts.merge(c, 1, Integer::sum);

        // Check if this char's frequency requirement is now met
        if (required.containsKey(c) && 
            windowCounts.get(c).intValue() == required.get(c).intValue()) {
            formed++;
        }

        // Shrink: while window is valid, try to minimize
        while (formed == requiredSize) {
            // Record minimum
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }

            // Remove s[left] from window
            char leftChar = s.charAt(left);
            windowCounts.merge(leftChar, -1, Integer::sum);

            if (required.containsKey(leftChar) && 
                windowCounts.get(leftChar) < required.get(leftChar)) {
                formed--;
            }
            left++;
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}

Complexity: O(n + m) time where n = |s|, m = |t|. O(n + m) space.

Common Mistakes:

• Using >= instead of == when incrementing formed (would count the same character multiple times)
• Not using .intValue() when comparing Integer objects (autoboxing comparison bug for values > 127)
• Forgetting to check required.containsKey(c) before comparing counts (NPE on characters not in t)
• Returning s.substring(left, left + minLen) instead of using the saved minLeft (left has moved!)

When Two Pointers Fails

Not every problem with pairs or subarrays is a two-pointer problem. Here are cases where it looks like two pointers but is not:

Common Mistakes

Practice Problems

Two Pointers

Sliding Window

Interview Tips

Signals You Are Solving Well

The 30-Second Pattern Selection Framework

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart TD
    A["Read the problem"] --> B{"Contiguous subarray/substring?"}
    B -->|"Yes"| C{"Fixed or variable size?"}
    B -->|"No"| D{"Sorted or can sort?"}

    C -->|"Fixed"| E["Fixed Sliding Window"]
    C -->|"Variable: longest"| F["Expand + shrink when invalid"]
    C -->|"Variable: shortest"| G["Expand until valid + shrink while valid"]

    D -->|"Yes"| H{"Pairs/triplets?"}
    D -->|"No"| I["HashMap / other pattern"]

    H -->|"Yes"| J["Opposite-end Two Pointers"]
    H -->|"No"| K["Binary Search likely better"]

    style E fill:#DCFCE7,stroke:#16A34A,color:#14532D
    style F fill:#DBEAFE,stroke:#2563EB,color:#1E3A5F
    style G fill:#FEF3C7,stroke:#D97706,color:#78350F
    style J fill:#DCFCE7,stroke:#16A34A,color:#14532D

Was this helpful?

Yes Needs more

Thanks for your feedback!

Discussion

Markdown supported Post

Sign in to join the discussion Sign In

Loading comments...