Two pointers and sliding window: two patterns that solve dozens of array problems

Many array and string questions look like they need two nested loops. These two patterns replace the inner loop by moving indexes smartly, cutting O(n²) to O(n).

Recognise them

• Two pointers: the array is sorted (or you can sort it) and you look for a pair, or you compare elements from both ends. One pointer starts at each end and they move towards each other.
• Sliding window: the question says "contiguous subarray" or "substring" with a condition such as a maximum sum, at most k distinct characters, or no repeats. Grow the window on the right; shrink it from the left when the condition breaks.

function pairWithSum(sorted, target) {
  let i = 0, j = sorted.length - 1;
  while (i < j) {
    const sum = sorted[i] + sorted[j];
    if (sum === target) return [sorted[i], sorted[j]];
    if (sum < target) i++; else j--;
  }
  return null;
}
function maxSumOfK(a, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += a[i];
  let best = sum;
  for (let i = k; i < a.length; i++) { sum += a[i] - a[i - k]; best = Math.max(best, sum); }
  return best;
}
function longestWithoutRepeats(s) {
  const lastSeen = new Map();
  let start = 0, best = 0;
  for (let end = 0; end < s.length; end++) {
    if (lastSeen.has(s[end]) && lastSeen.get(s[end]) >= start) start = lastSeen.get(s[end]) + 1;
    lastSeen.set(s[end], end);
    best = Math.max(best, end - start + 1);
  }
  return best;
}
console.log(pairWithSum([1, 3, 4, 6, 8, 11], 10));
console.log(maxSumOfK([2, 1, 5, 1, 3, 2], 3));
console.log(longestWithoutRepeats('abcabcbb'), longestWithoutRepeats('pwwkew'));

[ 4, 6 ]
9
3 3

Why they are O(n)

• In pairWithSum, every step moves i forward or j back, so the loop runs at most n times. If the sum is too small, only moving i right can increase it; if too big, only moving j left can decrease it.
• In maxSumOfK, the window slides by adding the new element and subtracting the one that left, instead of re-adding k numbers each time.
• In longestWithoutRepeats, start only ever moves forward, so each character enters and leaves the window once.

Practice list

Pair with a given sum, removing duplicates from a sorted array in place, container with most water, maximum sum subarray of size k, longest substring without repeating characters, smallest subarray with sum at least k. Find more in UniCircle interview prep: data structures and algorithms.