Walking In From Both Ends

Three problems that share one loop: a pointer at each end of the array, walking inward until they meet. They ask completely different questions - which pair sums to a target, is this a palindrome, which two walls hold the most water - and the difference between them is a single comparison in the middle.

What to watch for on this page is not the code. It is the argument each problem makes for why the pointer it moves is safe to give up on forever.

2 Sum in a sorted array

Given a sorted array and a target, find the pairs that sum to it. The nested-loop version is O(n²); the hash-map version is O(n) but allocates a table and gives up the sorted order. The two-pointer version is O(n), allocates nothing, and falls out of one observation.

a[lo] is paired with the largest value available, and a[hi] with the smallest. So a sum that lands short is not a rejection of that pair, it is a rejection of a[lo] against everything left, and a sum that overshoots rejects a[hi] the same way. Step through it and watch the greyed-out region grow - those are the pairs the algorithm never examines.

Two details that are easy to get wrong. The loop condition is lo < hi and not lo <= hi, because a value is not allowed to pair with itself. And after a hit, both pointers move: keeping either one fixed only re-finds the same pair, or a duplicate of it if the array holds repeats, which is what the two skip loops in the code below are for.

function twoSumSorted(a, target) {
  const pairs = [];
  let lo = 0, hi = a.length - 1;

  while (lo < hi) {
    const sum = a[lo] + a[hi];
    if (sum === target) {
      pairs.push([a[lo], a[hi]]);
      lo++; hi--;
      while (lo < hi && a[lo] === a[lo - 1]) lo++;   // skip duplicate lefts
      while (lo < hi && a[hi] === a[hi + 1]) hi--;   // skip duplicate rights
    } else if (sum < target) {
      lo++;
    } else {
      hi--;
    }
  }
  return pairs;
}

Sentence palindrome

Is a sentence a palindrome once case, spaces and punctuation are ignored? The same converging loop, with equality in the middle instead of a sum, and one wrinkle: each pointer has to skip characters that do not count.

The wrinkle matters more than it looks. Skipping is per pointer, not symmetric - the left pointer might step over three punctuation marks while the right one stays put. Written as one combined skip, the code drifts out of alignment and starts comparing the wrong characters. Written as two separate guards before the comparison, it stays honest.

Notice that a mismatch ends the run immediately. A palindrome check is the cheap case of the technique: it usually fails long before the pointers meet, and there is no reason to keep looking once one pair disagrees.

const isAlnum = (c) => /[a-z0-9]/i.test(c);

function isPalindromeSentence(s) {
  let lo = 0, hi = s.length - 1;

  while (lo < hi) {
    // Each pointer skips on its own. Combining these two loops into one
    // is the classic bug: the pointers fall out of step.
    if (!isAlnum(s[lo])) { lo++; continue; }
    if (!isAlnum(s[hi])) { hi--; continue; }

    if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
    lo++; hi--;
  }
  return true;
}

The O(1) space is the point of doing it this way. Stripping the string down to its letters first and comparing it against its own reverse is two lines and perfectly readable, but it builds two new strings to answer a yes/no question.

Container with most water

An array of wall heights, one unit apart. Pick two walls; the water they hold is min(height[i], height[j]) multiplied by the distance between them. Which pair holds the most?

Every pair is O(n²) again, and the greedy instinct - pick the two tallest walls - is wrong, because two tall walls standing next to each other hold almost nothing. What makes one pass enough is this: start at the widest possible pair, so width is at its maximum and can only get worse from here. Any move inward has to be paid for in height.

Now ask which wall to move. The water level is pinned to the shorter wall. Moving the taller one inward loses width and cannot raise the level, because the shorter wall still caps it - every container you could reach that way is worse than the one you have. So the only move that can possibly help is moving the shorter wall, and moving it retires that wall against every partner it had left.

function maxArea(height) {
  let lo = 0, hi = height.length - 1;
  let best = 0;

  while (lo < hi) {
    best = Math.max(best, Math.min(height[lo], height[hi]) * (hi - lo));

    // Only the shorter wall is worth moving: moving the taller one
    // loses width and cannot raise the water level.
    if (height[lo] <= height[hi]) lo++;
    else hi--;
  }
  return best;
}

The three side by side

None of the three needs an extra data structure, and all three are O(n) once the input is in the right order - which for the last two costs nothing, since neither needs sorting at all.

Check yourself

Next: the same trick with both pointers moving forward - sliding windows, in-place rewrites and reversing the words of a sentence.