DSA Patterns for Coding Interviews: The Techniques Behind Almost Every Problem

Part 3 of 16 · ~5 min

Two Pointers & Sliding Window

The registrar has a request: a student is exactly 7 credits short of graduating, and needs to know whether any two of this term's open electives add up to precisely that. Here's the sizes, already sorted, from the department's spreadsheet:

const sortedCredits = [1, 2, 3, 4, 5];   // sorted — hang onto that fact, it matters in a minute

Checking every pair costs O(n²). Two pointers replaces the pair check with two indices sweeping the array once, O(n) — and it splits into two genuinely different moves. Confusing them is the easiest way to fumble this pattern with the clock running.

Opposite-ends two pointers

Start one index at each end and close the gap:

function twoElectivesSumTo(sortedCredits, target) {
  let left = 0, right = sortedCredits.length - 1;
  while (left < right) {
    const sum = sortedCredits[left] + sortedCredits[right];
    if (sum === target) return true;
    if (sum < target) left++;     // too small — the only way up is a bigger left value
    else right--;                 // too big — the only way down is a smaller right value
  }
  return false;
}

twoElectivesSumTo(sortedCredits, 7);  // (1,5)=6, too small → left++; (2,5)=7 → true

Two steps and it's found: left=0 (1) against right=4 (5) sums to 6, short of 7, so left advances. left=1 (2) against right=4 (5) sums to 7. Done — nowhere near the fifteen pairwise checks a nested loop would run.

Sortedness is doing all the work. Every value between the old left and the new one is no larger than sortedCredits[left] was, so if the pair already fell short of the target, sliding left rightward is the only move that can possibly raise the sum — nothing to the left of the old position could have helped. The mirror argument covers right--. Because each pointer commits to a direction and never reverses, the total number of steps across the whole run tops out at n, not n².

Keep that sortedness assumption in mind. The next chapter takes it away.

Same-direction two pointers

This variant shows up somewhere else entirely: rewriting an array in place instead of searching it, or running two pointers at unequal speeds over the same chain of data.

A transfer student's imported transcript arrives sorted by course code, but a records bug has duplicated some rows:

function dedupeSortedTranscript(codes) {
  if (codes.length === 0) return 0;
  let slow = 0;                              // slow marks the end of the cleaned-up region so far
  for (let fast = 1; fast < codes.length; fast++) {
    if (codes[fast] !== codes[slow]) {
      slow++;
      codes[slow] = codes[fast];
    }
  }
  return slow + 1;                           // length of the deduplicated prefix
}

fast scouts ahead; slow only steps forward once something genuinely new turns up. Most in-place partitioning runs on exactly this mechanic, and so does Floyd's cycle detection — which the planner needs a few features later. Each course can optionally point to a "students who finish this usually take next" suggestion, chaining into a linked list. A data-entry slip once made course D's suggestion loop back to course B, three steps earlier — invisible if you only ever print a handful of suggestions at a time.

function hasSuggestionCycle(start) {
  let slow = start, fast = start;
  while (fast && fast.next) {
    slow = slow.next;               // one hop
    fast = fast.next.next;          // two hops
    if (slow === fast) return true; // fast caught up from behind — there's a loop
  }
  return false;
}

slow takes one step per iteration, fast takes two. On a straight chain, fast simply reaches the end. Inside a loop, fast keeps re-entering it faster than slow and eventually catches up from behind — no Set of visited nodes required.

Sliding window — fixed size

Two weeks before finals, the planner starts flagging a student's roughest upcoming stretch — given each remaining day's already-committed study hours, which 3-day block carries the heaviest total?

function heaviestKDayStretch(dailyHours, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += dailyHours[i];   // build the first window once

  let maxSum = windowSum;
  for (let i = k; i < dailyHours.length; i++) {
    windowSum += dailyHours[i] - dailyHours[i - k];   // add the incoming day, drop the outgoing one
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

Recomputing every 3-day total from scratch costs O(n·k). Keep a single running total instead, and each step only needs two operations — fold in the day that just entered the window, remove the day that just left it — which drops the whole scan to O(n). No day, once counted, ever gets looked at a second time.

Sliding window — variable size

Advisors want a flag for students cramming one course repeatedly instead of spreading study time: the longest run of consecutive study-log days with no repeated course.

function longestNoRepeatStreak(studyLog) {           // studyLog: one course code per day
  const seen = new Set();
  let left = 0, longest = 0;

  for (let right = 0; right < studyLog.length; right++) {
    while (seen.has(studyLog[right])) {      // shrink until the repeat is gone
      seen.delete(studyLog[left]);
      left++;
    }
    seen.add(studyLog[right]);
    longest = Math.max(longest, right - left + 1);
  }
  return longest;
}

right grows the window a day at a time; the while beneath it only fires when the day it's about to add is already inside the window. On paper that's two loops, which smells like O(n²). It isn't: left marches strictly forward for the entire run and can advance at most n times total across every iteration of the outer loop combined, so the two loops together still add up to O(n). The monotonic stack a couple of chapters ahead leans on this exact accounting trick — total the work across the whole run instead of pricing a single iteration on its own.

Telling the two families apart on sight comes down to what the data looks like and what's being asked. Reach for two pointers when something is already ordered and you're either hunting a target pair or rearranging entries without extra storage. Reach for a window instead when the question is about an unbroken run — consecutive days, adjacent characters, a stretch of an array — phrased as longest, shortest, or a count of something inside it, where the edges of that run shift in response to a rule rather than sitting at fixed positions.

Both get their own timed problem sets on Code Lab, under Two Pointers and Sliding Window.