Two pointers

The shape of the pattern

Two pointers means walking a structure with two indices instead of nested loops. Whenever you're tempted to check every pair (i, j) against each other, ask: does the data have an order I can exploit so the pointers only ever move forward, never backward? If yes, two pointers turns O(n²) pair-checking into a single O(n) pass.

Variant 1 — opposite ends, closing inward

Used on sorted arrays where you need a pair that satisfies some condition.

// Two Sum on a SORTED array — O(n) time, O(1) space
function twoSumSorted(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;   // need bigger → drop the smaller end
    else right--;               // need smaller → drop the bigger end
  }
  return [-1, -1];
}

Why this is correct, not just fast: because the array is sorted, moving left past the current value can never re-find a pair we already ruled out — every skipped pair genuinely can't work.

Dry run: twoSumSorted([2, 7, 11, 15, 18, 24], 22)

Six elements, but only four comparisons — each one eliminates an entire end of the remaining range, not just one element. That's the O(n) behavior: the pointers together take at most n steps total to meet.

Variant 2 — fast/slow, same direction

Both pointers start at the same end but move at different rates (or one waits while the other scans). This is the shape behind removing duplicates in place, partitioning, and cycle detection in linked lists.

// remove duplicates from a SORTED array, in place — O(n) time, O(1) space
function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let slow = 0; // slow = last confirmed-unique position
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
  return slow + 1; // count of unique elements
}

Variant 3 — palindrome / mirror check

function isPalindrome(s) {
  let left = 0, right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

Container with most water: proving the move is safe

You are given the heights of n vertical lines. Pick two of them; together with the x-axis they hold water as deep as the shorter line and as wide as the gap between their indices. Find the largest area. Checking every pair is O(n²).

Start with the widest container, the two ends. Every other container is narrower, so to beat the one you hold it needs a taller wall, and the wall that limits you is the shorter one. Now look at what a move does. Moving the taller wall inward shrinks the width by one and leaves the shorter wall in charge, so the area cannot grow. Moving the shorter wall inward also costs width, but it is the only move that can find something taller. That says which pointer to move. The next step is to show it throws nothing useful away.

function maxArea(height) {
  let left = 0, right = height.length - 1, best = 0;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    best = Math.max(best, area);
    if (height[left] < height[right]) left++;  // the shorter wall limits us: drop it
    else right--;                              // equal or taller on the left: drop the right
  }
  return best;
}

Dry run: maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])

Eight steps for nine lines, and every step discarded one index. That is O(n) time and O(1) space. The best container, 49, is the pair of lines of height 8 and 7, found on the second step; the rest of the scan only proves nothing beats it.

3Sum: sort, fix one, scan the rest

Find every unique triplet in the array that adds up to zero. The brute force tries every triple, O(n³), and then has to remove repeated triplets, which usually means building strings or sets of them. Two pointers removes both costs.

Sort first. Now fix the smallest element of the triplet at position i. What remains is a question you already solved: find two values in the sorted part to the right of i that add up to -a[i]. That is twoSumSorted, an O(n) scan. Running it once per i gives O(n²) in total, and sorting costs only O(n log n) on top.

Sorting also makes duplicates easy, because equal values sit next to each other. There are three places a repeated triplet can sneak in, and each has its own guard:

• The fixed value. If a[i] === a[i - 1], skip i. The earlier iteration already found every triplet whose smallest element has that value, including those that use the second copy as lo. Compare with the previous element, not the next one: comparing with the next would skip [-1, -1, 2].
• The left pointer. After a hit, move lo past every copy of the value you just used.
• The right pointer. Do the same for hi.

// O(n²) time after an O(n log n) sort; O(n) for the sorted copy
function threeSum(nums) {
  const a = nums.slice().sort((x, y) => x - y);  // numeric sort: the default one compares strings
  const out = [];
  for (let i = 0; i < a.length - 2; i++) {
    if (a[i] > 0) break;                         // the smallest is positive, so every sum is positive
    if (i > 0 && a[i] === a[i - 1]) continue;   // same fixed value as last time
    let lo = i + 1, hi = a.length - 1;
    while (lo < hi) {
      const sum = a[i] + a[lo] + a[hi];
      if (sum < 0) lo++;
      else if (sum > 0) hi--;
      else {
        out.push([a[i], a[lo], a[hi]]);
        lo++;
        hi--;
        while (lo < hi && a[lo] === a[lo - 1]) lo++;   // step past copies of the value just used
        while (lo < hi && a[hi] === a[hi + 1]) hi--;
      }
    }
  }
  return out;
}

Dry run: threeSum([-1, 0, 1, 2, -1, -4])

Sorted copy: [-4, -1, -1, 0, 1, 2].

The answer is [[-1, -1, 2], [-1, 0, 1]]. Without the skip at i = 2, that iteration would find [-1, 0, 1] a second time.

k-Sum and 3Sum closest: the same scan, generalised

4Sum is 3Sum with one more fixed value, and 5Sum with one more still. The pattern is a recursion: for k > 2, fix one value and ask for a (k - 1)-sum on what remains to its right; at k = 2, run the two-pointer scan. Each level is a loop with the same duplicate guard on the fixed value, so you write the guard once.

// all unique k-tuples (k >= 2) summing to target; O(n^(k-1)) after the sort
function kSum(nums, target, k) {
  const a = nums.slice().sort((x, y) => x - y);
  return collect(a, 0, target, k);
}

function collect(a, start, target, k) {
  const out = [];
  if (start + k > a.length) return out;
  if (a[start] * k > target || a[a.length - 1] * k < target) return out; // no k values can reach it

  if (k === 2) {
    let lo = start, hi = a.length - 1;
    while (lo < hi) {
      const sum = a[lo] + a[hi];
      if (sum < target) lo++;
      else if (sum > target) hi--;
      else {
        out.push([a[lo], a[hi]]);
        lo++;
        hi--;
        while (lo < hi && a[lo] === a[lo - 1]) lo++;
        while (lo < hi && a[hi] === a[hi + 1]) hi--;
      }
    }
    return out;
  }

  for (let i = start; i < a.length - k + 1; i++) {
    if (i > start && a[i] === a[i - 1]) continue;
    for (const rest of collect(a, i + 1, target - a[i], k - 1)) out.push([a[i], ...rest]);
  }
  return out;
}

The early exit is a bound, not a heuristic: the smallest possible sum of k values taken from a[start..] is k * a[start], and the largest is k * a[a.length - 1]. If the target lies outside that range, no tuple exists. The time is O(n^k−1): each added level multiplies the work by n, and the two-pointer base replaces the last loop. Say that number aloud; it is what separates "I know 4Sum" from "I know the family".

3Sum closest asks for the triple whose sum is nearest to the target. The scan is identical, except that you no longer wait for an exact match. Keep the best sum seen so far, and move the pointer that brings the sum toward the target.

// needs at least 3 numbers; O(n²)
function threeSumClosest(nums, target) {
  const a = nums.slice().sort((x, y) => x - y);
  let best = a[0] + a[1] + a[2];
  for (let i = 0; i < a.length - 2; i++) {
    let lo = i + 1, hi = a.length - 1;
    while (lo < hi) {
      const sum = a[i] + a[lo] + a[hi];
      if (Math.abs(sum - target) < Math.abs(best - target)) best = sum;
      if (sum === target) return sum;
      if (sum < target) lo++;
      else hi--;
    }
  }
  return best;
}

No duplicate guards are needed, because the function returns one number, not a list of triplets; repeated work only costs time, and the sorted scan is already O(n²).

Trapping rain water: three ways to the same answer

After rain, how much water sits on top of an elevation map given as an array of non-negative bar heights? Think one column at a time. The water above bar i rises to the lower of the tallest bar on its left and the tallest bar on its right (each counting bar i itself), so the water in that column is min(maxLeft, maxRight) - height[i].

Version 1: precompute both maxima. Two passes fill leftMax[] and rightMax[]; a third adds up the columns. It is the easiest to get right and is O(n) time with O(n) space.

function trapWithArrays(height) {
  const n = height.length;
  if (n === 0) return 0;
  const leftMax = new Array(n), rightMax = new Array(n);
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);

  let water = 0;
  for (let i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];
  return water;
}

Version 2: two pointers, O(1) space. The arrays are only there to answer "which side is lower?" for one column at a time. Two pointers answer it without storing anything. Keep a running leftMax and rightMax and always advance the pointer on the lower wall.

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0, water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];   // settled: the right side is at least as tall
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

Dry run: trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])

The pointers meet at index 7, the tallest bar, which holds no water, and the total is 6. Each step consumed one column, so the work is O(n) with O(1) extra space.

Version 3: a monotonic stack. Instead of counting water column by column, count it in horizontal layers. Keep a stack of bar indices whose heights decrease from bottom to top. When a taller bar arrives, the bar on top of the stack is the bottom of a pocket: the stack entry beneath it is the left wall, the new bar is the right wall, and the layer's water is width * (min(leftWall, rightWall) - bottom). It is also O(n) time with O(n) space, and it is the same pop-when-a-bigger-one-arrives idea you meet in monotonic stacks.

function trapWithStack(height) {
  const stack = [];   // indices, heights decreasing from bottom to top
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop();
      if (stack.length === 0) break;              // no left wall: nothing to hold the water
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      water += width * (Math.min(height[left], height[i]) - height[bottom]);
    }
    stack.push(i);
  }
  return water;
}

Fast and slow in place: filter, keep at most two, move zeroes

The duplicate-removal loop above is one instance of a shape worth naming. The read pointer looks at every element once. The write pointer marks the end of the part you have decided to keep. The invariant is a sentence you can say aloud: nums[0..write) is the correct answer for nums[0..read). Every in-place filter is that sentence with a different rule for "keep".

// remove every copy of val; return the new length
function removeElement(nums, val) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== val) nums[write++] = nums[read];
  }
  return write;
}

// move all zeroes to the end, keeping the order of the others
function moveZeroes(nums) {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      [nums[write], nums[read]] = [nums[read], nums[write]];
      write++;
    }
  }
}

// sorted array: keep at most k copies of each value; return the new length
function keepAtMost(nums, k) {
  let write = 0;
  for (const x of nums) {
    if (write < k || x !== nums[write - k]) nums[write++] = x;
  }
  return write;
}

keepAtMost is the dedupe loop with the comparison pushed back. A value may be written unless the kept prefix already ends in k copies of it, which, because the prefix is sorted, is the same as nums[write - k] === x. Compare against the written prefix, not the original array: the original may already be overwritten. With k = 1 this is exactly removeDuplicates; with k = 2 it is the usual "remove duplicates, allow two" question.

All three are O(n) time and O(1) space, and each element is read once. The moveZeroes swap does a pointless self-swap while write === read, which is harmless; if the interviewer cares about the number of writes, guard it with if (write !== read).

Three-way partition: the Dutch national flag

Sort an array that only contains 0, 1 and 2, in place, in one pass, without a counting pre-pass. This is the question that adds a third pointer. The idea is to split the array into four regions and keep each region honest: everything before low is a 0, everything from low up to mid is a 1, everything after high is a 2, and the stretch from mid to high has not been looked at yet.

function sortColors(nums) {
  let low = 0, mid = 0, high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      swap(nums, low, mid);
      low++;
      mid++;                  // what came from low is a 1 we already saw
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      swap(nums, mid, high);
      high--;                 // do NOT move mid: the swapped-in value is unseen
    }
  }
}

function swap(arr, i, j) {
  const t = arr[i];
  arr[i] = arr[j];
  arr[j] = t;
}

Dry run: sortColors([2, 0, 2, 1, 1, 0])

Look at the first row: after swapping a 2 to the back, the value that landed at mid is the 0 that used to be at the end, and the loop looks at it again on the next step. That is the reason mid stays put in the 2 branch and moves in the 0 branch: the value swapped in from low has already been classified (it can only be a 1), but the value swapped in from high has not.

The array is touched in one pass. Each step either moves mid up or high down, and the unseen region has high - mid + 1 elements, so there are at most n steps: O(n) time, O(1) space. Nothing here is specific to the numbers 0, 1 and 2. Replace the three tests with < pivot, === pivot and > pivot and you have the three-way partition behind quicksort on arrays with many equal keys, covered in sorting algorithms.

Two sorted inputs: merge from the back, squares from the ends

Merging two sorted arrays into a new one is the base case: one pointer per array, always take the smaller head, O(m + n). The interview version adds a twist. The first array has room for both: it holds m real values followed by n empty slots, and you must merge in place.

Merge from the front and you overwrite values of the first array you have not read yet. Merge from the back instead: the largest remaining value belongs at the last free slot, and the slots at the back are exactly the ones nobody needs. Three pointers: i at the end of the real values of the first array, j at the end of the second, and k at the slot being written.

function mergeInto(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, k = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
    else nums1[k--] = nums2[j--];
  }
}

This is mergeInto([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3). The loop stops when nums2 is used up, because whatever remains of nums1 is already in its final place. Time O(m + n), space O(1).

Squares of a sorted array uses the same trick for a different reason. Squaring a sorted array with negatives gives a sequence that falls and then rises: the largest squares are at the two ends. So fill the output from the back with whichever end has the larger square.

function sortedSquares(nums) {
  const n = nums.length;
  const out = new Array(n);
  let left = 0, right = n - 1;
  for (let k = n - 1; k >= 0; k--) {
    const l = nums[left] * nums[left];
    const r = nums[right] * nums[right];
    if (l > r) { out[k] = l; left++; }
    else { out[k] = r; right--; }
  }
  return out;
}

On [-4, -1, 0, 3, 10] the picks are 100 (right), 16 (left), 9 (right), 1 (left), 0 (right), giving [0, 1, 9, 16, 100] in O(n), where squaring and then sorting would cost O(n log n). The idea to carry away: when the useful values collect at the ends, work from the ends inward and fill the output from its largest slot.

Expanding from the center: palindromes in both directions

Checking a palindrome moves two pointers inward. Finding the longest palindromic substring turns that around. You do not know where a palindrome starts or ends, but you do know that every palindrome has a center, and that growing outward from the center keeps it a palindrome exactly while the two new characters match. A string of length n has 2n - 1 centers: n single characters for odd lengths and n − 1 gaps between characters for even lengths.

function longestPalindrome(s) {
  let start = 0, bestLen = 0;

  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
    }
    return r - l - 1;                         // length of the palindrome that just stopped growing
  }

  for (let c = 0; c < s.length; c++) {
    const len = Math.max(expand(c, c), expand(c, c + 1));  // odd center, even center
    if (len > bestLen) {
      bestLen = len;
      start = c - Math.floor((len - 1) / 2);
    }
  }
  return s.slice(start, start + bestLen);
}

The loop stops one step too far, with l and r on the first mismatch or off the array, so the palindrome is s[l+1 .. r-1], which has length r - l - 1. The start formula works for both parities: for an odd length centered at c the start is c - (len - 1) / 2, and for an even length from the pair (c, c + 1) it is c - (len / 2 - 1), and Math.floor((len - 1) / 2) gives both.

Each of the 2n - 1 centers can expand up to about n/2 steps, so the worst case, a string such as "aaaa…a", is O(n²) time and O(1) space. That is a real improvement on checking every substring, which is O(n³), and a good place to stop unless the interviewer asks for more. (An O(n) algorithm exists, Manacher's; it is rarely expected.) Counting palindromic substrings is the same loop: add one for every successful step of the expansion instead of tracking the longest.

Valid palindrome, with and without a deletion

The most common variant ignores everything that is not a letter or a digit, and compares case-insensitively. Two pointers still close inward; each one first skips over characters that do not count.

function isPalindromeClean(s) {
  const isAlnum = (c) => /[a-z0-9]/i.test(c);
  let l = 0, r = s.length - 1;
  while (l < r) {
    while (l < r && !isAlnum(s[l])) l++;
    while (l < r && !isAlnum(s[r])) r--;
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++;
    r--;
  }
  return true;
}

Valid palindrome II allows deleting at most one character. Scan inward as usual. At the first mismatch (l, r), one of those two characters has to go: the characters outside them already match pairwise, so the only way to end with a palindrome is to drop s[l] or drop s[r]. Check both remaining ranges with a plain palindrome test; if either passes, the answer is yes.

function validPalindromeII(s) {
  function isRange(l, r) {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++;
      r--;
    }
    return true;
  }
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (s[l] !== s[r]) return isRange(l + 1, r) || isRange(l, r - 1);
    l++;
    r--;
  }
  return true;
}

The second scan only happens once, at the first mismatch, so the total is at most three passes over the string: O(n) time, O(1) space. Do not try to recurse on both branches at every mismatch: that is how an O(n) idea turns into O(2ⁿ). If you want to convince yourself that two candidates are enough, test the function against a brute force that deletes every position in turn on all short strings.

Two strings at once: backspace compare in O(1) space

Two strings contain letters and #, where # deletes the character before it. Are they equal after typing? The direct way builds both results with a stack and compares: O(n) time, O(n) space. To use O(1) space, scan from the end of both strings. Going backward, a # tells you exactly how many characters to the left to skip, so you never need to remember the letters you have not skipped yet.

function backspaceCompare(s, t) {
  let i = s.length - 1, j = t.length - 1;
  while (i >= 0 || j >= 0) {
    i = prevValid(s, i);
    j = prevValid(t, j);
    if (i < 0 && j < 0) return true;       // both strings ran out together
    if (i < 0 || j < 0) return false;      // only one ran out
    if (s[i] !== t[j]) return false;
    i--;
    j--;
  }
  return true;
}

// the index of the next character that survives the backspaces, scanning left from i; -1 if none
function prevValid(str, i) {
  let skip = 0;
  while (i >= 0) {
    if (str[i] === "#") { skip++; i--; }
    else if (skip > 0) { skip--; i--; }
    else break;
  }
  return i;
}

On "ab#c" and "ad#c": both scans start on c and match. The next call walks left over # (skip becomes 1), then over b or d (skip back to 0), and stops on a in both, which also match. Both indices are now −1, so the answer is true. Each index only moves left, so the time is O(n + m) and the space is O(1). The reason the scan must go backward is that a # only affects what is before it.

Next permutation: a pivot, a swap and a reverse

Rearrange an array into the next larger arrangement in lexicographic order, or the smallest one if it is already the largest, in place. The arrangement [1, 3, 5, 4, 2] is followed by [1, 4, 2, 3, 5]. There is nothing to search; the result follows from three observations.

• A suffix that is non-increasing (each value no larger than the one before) is already the largest arrangement of its own values, so you cannot get a larger one by touching only that suffix. Find the longest such suffix. The element just before it, the pivot, is the first one you can raise. If there is no pivot, the whole array is the largest permutation: reverse it and stop.
• To make the array larger by the smallest possible step, raise the pivot to the smallest value in the suffix that is larger than it. Because the suffix is non-increasing, scanning from the right finds it first.
• After the swap the suffix is still non-increasing. The smallest arrangement of those values is the increasing one, and reversing a non-increasing run produces it in O(n).

function nextPermutation(nums) {
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;      // pivot: last place where the order goes up
  if (i >= 0) {
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) j--;                  // rightmost value strictly larger than the pivot
    swap(nums, i, j);
  }
  reverseRange(nums, i + 1, nums.length - 1);
}

function reverseRange(arr, lo, hi) {
  while (lo < hi) swap(arr, lo++, hi--);
}

On [1, 3, 5, 4, 2]: the suffix [5, 4, 2] is non-increasing, so the pivot is the 3 at index 1. The rightmost value larger than 3 is the 4 at index 3. Swap them to get [1, 4, 5, 3, 2], then reverse the suffix after index 1 to get [1, 4, 2, 3, 5]. Time O(n), space O(1). The two comparisons use >= and <= so that equal values are handled: with duplicates, a strict test would stop on an equal pair, which is not a place where the order goes up.

Fast and slow on linked lists: middle, cycle, cycle start

On a linked list you cannot jump to index n/2, but you can send two walkers: slow moves one node per step and fast moves two. When fast runs off the end, slow is in the middle, because it travelled half as far. If there is a cycle, fast never runs off the end, so the question becomes whether the two meet.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// for an even count this returns the second of the two middle nodes
function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Why they must meet. Once both walkers are inside the cycle, the gap between them, measured along the cycle, shrinks by exactly one each step (fast gains one node on slow per step). A gap that shrinks by one at a time cannot jump over zero, so they meet within one cycle length of steps. That is the reason for speeds 1 and 2: their difference is exactly one node per step.

Where the cycle starts. Let a be the number of nodes before the cycle, c the cycle length, and suppose the walkers meet k steps into the cycle. Slow has travelled a + k (it has not completed a lap yet, since the gap closes within one cycle length); fast has travelled 2(a + k), which equals a + k plus some whole number of laps. So a + k is a multiple of c, which means a steps from the meeting point lands exactly on the cycle's entrance. Start one pointer at the head and keep the other at the meeting point, move both one node at a time, and they meet at the entrance.

function cycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let p = head;
      while (p !== slow) {
        p = p.next;
        slow = slow.next;
      }
      return p;
    }
  }
  return null;
}

On the list 3 → 2 → 0 → −4 → 5 → 6 where the last node points back to the 2: the walkers meet at the 6 after five steps. Then a pointer from the head and one from the 6 step together: both land on the 2 after one move. Here a = 1, c = 5, and the first meeting is at k = 4, and indeed a + k = 5 = c. All three functions are O(n) time and O(1) space. The same idea finds a duplicate in an array treated as a linked list, which you will meet in binary search as the alternative to a value-range search.

Which shape for which problem

Ask three questions. Is there an order (or a sortable one) that tells me which pointer to drop? Am I building an output in place? Do the two things I move live in one sequence or in two? The answers choose a row of the table.

Pitfalls that cost offers

• Using the opposite-ends scan on unsorted data gives wrong answers with no error. Sort first, or use a hash map.
• left <= right where left < right is meant pairs an element with itself. Decide whether the pointers may coincide, and write that in the loop condition.
• Duplicate handling in k-Sum. Skip against the previous element for the fixed value, and step past equal values after a hit. Both rules must be present or you return the same triplet twice, or miss one.
• Sorting destroys positions. If the answer is indices (classic Two Sum on an unsorted array), sorting loses them, unless you sort pairs of (value, index). A hash map is usually simpler.
• The default sort() compares strings. Always pass (a, b) => a - b for numbers.
• Mutating the input without saying so. In-place problems expect it; problems that return a new structure usually do not. Copy with slice() before sorting when the caller keeps the original.
• Moving mid after a swap with high in the three-way partition skips an unseen element.
• Comparing against the original array in a read/write loop instead of the written prefix, after the original has been overwritten.
• Empty and tiny inputs. Zero, one and two elements break loops that start at nums.length - 2, a[0] + a[1] + a[2] or height.length - 1 unless guarded.

How to recognize it in an unseen problem

• The input is sorted (or can be sorted without losing what you need)
• You're looking for a pair, triplet, or a "does X exist" over combinations
• A brute force would be nested loops comparing indices against each other
• The words "sorted array," "pair," or "in-place" appear in the prompt
• The answer is built in place and the prompt asks for O(1) extra space: a read pointer and a write pointer
• Two sorted sequences must be combined, or a sorted array must be transformed and kept sorted
• A string must read the same from both ends, possibly after one deletion, or you must find the longest such stretch
• A linked list needs its middle, or a check for a cycle, without extra memory

Three Sum is the natural extension: sort once, then fix one index and run the opposite-ends two-pointer scan on the rest — O(n²) total instead of the O(n³) brute force, because the inner two-sum collapses from a nested loop to a linear scan.

See it move

Step through it and watch why a pointer moves. Every move rules out a whole block of pairs at once — that is the entire reason this beats the nested loop.