Two pointers & sliding window

Two pointers and the sliding window are the patterns that most often replace an order n squared brute force with an order n pass over arrays and strings. The shared idea is that you keep a small amount of state as you move through the data, rather than recomputing from scratch at every position. Once you see them, a huge class of array and string problems looks the same.

// two pointers: is a string a palindrome?
function isPalindrome(s) {
  let i = 0, j = s.length - 1;
  while (i < j) {
    if (s[i] !== s[j]) return false;
    i++; j--;
  }
  return true;
}

Two pointers

Two pointers place indices at different positions and move them toward each other or in the same direction. On a sorted array you can find a pair summing to a target by moving the left pointer up when the sum is too small and the right pointer down when it is too large. You never need a nested loop because each step makes provable progress and each pointer crosses the array at most once.

Sliding window

A sliding window keeps a contiguous range and slides it forward, adding the new element on the right and removing the old one on the left. The key is updating a running summary, such as a sum or a character count, incrementally instead of rescanning the window. A fixed-size window finds things like the maximum sum of any k consecutive elements; a variable window finds the longest substring without repeating characters by shrinking from the left whenever the constraint breaks.

The challenge below slides a fixed-size window of length k across an array and reports the maximum sum, updating the running total in constant time per step.

Next: stacks and queues, and the order in which work comes back out.