← dsa.gleee.in Hub
DSA · 01

Two Pointers & Sliding Window

Google Interview Cheat Sheet — Two Pointers & Sliding Window

Amortized O(N) · Max 2N Pointer Moves

1. Pattern Triggers

  • Sliding Window: Contiguous subarray or substring asking for "longest", "shortest", or frequency constraints.
  • Opposite Two Pointers: Sorted array pair sums, palindromes, or pairwise optimization (e.g., Container With Most Water) where one end can be greedily eliminated.
  • Watch Out: Negative numbers break sum-based sliding window monotonicity—use Prefix Sum + HashMap instead.

2. Loop Invariant Template

var left = 0
for (right in s.indices) {
    // 1. Expand R -> update state
    while (!isValid(state)) {
        // 2. Shrink L -> remove s[left]
        left++
    }
    // 3. Invariant holds -> update best
    best = maxOf(best, right - left + 1)
}

3. Amortized O(N) Proof

  • Interviewers often ask: "Isn't a while loop inside a for loop O(N²)?"
  • Proof: Both L and R start at 0 and only move rightward.
  • Each index is added at most once by R and removed at most once by L → at most 2N pointer operations total = O(N)!
◉ Longest Unique Substring · s = "abcaefcb"
Invariant Holds
Step 1 / 12
◆ Step Breakdown & Loop Invariant
INIT

Loading...

Google Interviewer Lens

{ } LongestUniqueSubstring.kt
O(N) Time · O(min(N, Σ)) Space
Keyboard shortcuts: ← / → Step · Space Play/Pause · R Reset