Level 1 · 30 min

Arrays & Strings: The Two-Pointer Toolkit

Arrays and strings underlie nearly every interview problem. The two-pointer pattern (Cracking the Coding Interview chapter 1) reduces many quadratic problems to linear time by exploiting structural properties — sortedness, palindromes, or sliding windows over contiguous data.

The Two-Pointer Pattern

Two pointers traverse the array in a coordinated way: opposite-ends (start and end converge, e.g. valid palindrome, two-sum sorted), same-direction (slow and fast move at different speeds), or sliding window (left and right define a current range). The invariant is what makes the pattern correct: e.g. for two-sum sorted you maintain ''sum of a[lo] + a[hi] either equals target, is too small (advance lo), or is too large (decrement hi)''. CLRS chapter 2 introduces invariants formally — initialization, maintenance, termination — and they are the primary tool for proving array-algorithm correctness.

Sliding Window

A sliding window is a two-pointer variant where you grow the right edge to include new elements and shrink the left edge to maintain a constraint (sum bounded, distinct chars, no duplicates). Classic problems: longest substring without repeating chars (O(n) with a HashMap of char to last index), minimum window substring (O(n+m) with character frequency counters), max sum subarray of size k (O(n) by adjusting the running sum). The key insight is that each element enters and leaves the window at most once, giving amortized O(1) per step and O(n) total. Cracking ch. 1 problem 1.5 ''one edit away'' is a near-miss two-pointer — the pointers advance asymmetrically depending on edit type.

Strings: Mutability and Encoding

Java/Python/JS strings are immutable: every concatenation builds a new string. To build a string of length n with += in a loop you do O(n^2) work. Use StringBuilder (Java), io.StringIO (Python), or array.join() (JS/Python) to amortize to O(n). Encoding traps: ''length'' in JS counts UTF-16 code units, so emoji of length-2 code units appear as length 2 — use Array.from(str).length to count user-perceived characters. Reversing a UTF-16 string by char swap can split surrogate pairs and produce invalid Unicode; reverse code points, not code units. CLRS chapter 32 (string matching) is the deeper reference for KMP, Rabin-Karp, and Boyer-Moore.

Key Takeaways

Two pointers reduce many O(n^2) array problems to O(n) — but require a sorted or monotonic property to apply.
Sliding window: each element enters and leaves at most once. Total work is O(n) regardless of window size.
Never do += on a string in a loop. Use StringBuilder / join() to avoid O(n^2) blowup.

Code example

// Java — sliding window for longest substring without repeats
int longestUnique(String s) {
  Map<Character, Integer> lastIdx = new HashMap<'>();
  int best = 0, left = 0;
  for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    if (lastIdx.containsKey(c) '&'&' lastIdx.get(c) >= left) {
      left = lastIdx.get(c) + 1;
    }
    lastIdx.put(c, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

// Two-pointer palindrome (handles odd/even and case-insensitivity)
boolean isPalindrome(String s) {
  int lo = 0, hi = s.length() - 1;
  while (lo < hi) {
    while (lo < hi '&'&' !Character.isLetterOrDigit(s.charAt(lo))) lo++;
    while (lo < hi '&'&' !Character.isLetterOrDigit(s.charAt(hi))) hi--;
    if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi)))
      return false;
    lo++; hi--;
  }
  return true;
}