Two Pointers pattern · DSA & System Design

30-second answer

Two fingers on a row replace a nested loop with one pass, because every step rules out an element for good.

Roadmap and prerequisites

Two pointers is the first pointer pattern. Learn it well and sliding window, fast and slow pointers and merging come almost free.

Where it fits

Prerequisites

You should know	Why it matters here	Quick check
Indexing and loops	Pointers are indexes. Off-by-one is the top bug.	What does `arr[arr.length]` give?
Sorting with a comparator	Many problems start with a sort.	Why is `[10, 9, 1].sort()` equal to `[1, 10, 9]`?
Big-O	To see why one pass beats two loops.	How many pairs are in 1,000 items?
Invariants	Every pointer move needs a reason.	What is true outside `left..right`?
Destructuring swap	In-place edits.	What does `[a, b] = [b, a]` do?

Why this pattern exists

Checking every pair costs n(n - 1) / 2 steps. For 100,000 numbers that is about 5 billion. Two pointers makes at most n - 1 moves, because each move rules one element out. That is 99,999 for the same input.

How it connects to other patterns

Hashing solves the same pair problems on unsorted data, but uses O(n) memory.
Sliding window is two pointers that move the same way and guard the range between them.
Binary search is lo and hi closing in on an answer.
Fast and slow pointers use two speeds instead of two directions.
Greedy gives the proof for moves like "drop the shorter wall".

Learning sequence

Must know. Reverse in place, then Valid Palindrome: two ends moving inward.
Must know. Pair sum on a sorted array: the move depends on a comparison.
Must know. Read and write pointers: Move Zeroes, remove duplicates.
Merge two sorted inputs: one pointer per input.
Reduce k-sum to pair sum: 3Sum, with duplicate skipping.
Container With Most Water: a move you must prove.
Advanced. Trapping Rain Water and three-way partitioning: two or three pointers with extra state.

Arrays and strings
  Hash maps and sets      "have I seen this?" in O(1), any order
  Two pointers       <--  you are here: two indices, each move discards something
    Sliding window        same-direction pointers that keep a valid range
    Fast and slow         two speeds on a linked list or a number sequence
    Binary search         lo and hi: two pointers that halve the range

Recognition guide: when to use it, and when not to

A keyword never decides the pattern.

Strong signals

Signal	Why it points here	What you track
Sorted input, pair or triplet with a sum, difference or count	Order tells you which end to drop	`left`, `right`, the current sum
Compare something with its mirror (palindrome)	The two ends must match	`left`, `right`
In place, O(1) extra space, keep or remove some values	Read and write pointers compact the array	`read`, `write`
Two sorted inputs, merge or intersect	The next output is at one of two heads	One index per input
A bottleneck argument: the smaller side decides	You can settle the smaller side now	Running max on each side

Misleading signals

"Array" and "sum" do not mean two pointers. Unsorted data with a target needs a hash map. Counting subarrays with negatives needs prefix sums.
"Pair" means two pointers only when sorting is allowed and indexes do not matter. Sorting loses the original indexes.
"Subarray" usually means sliding window or prefix sums, not opposite ends.

Choosing between the three shapes

Shape	Pointers start	Move rule	Example
Opposite ends	`0` and `n - 1`	Drop the end that cannot win	Pair sum, Container With Most Water
Read and write	Both at `0`	`read` always, `write` on keep	Move Zeroes
One per input	Start of each input	Take the smaller head	Merge sorted arrays

When to avoid it

No move can safely discard anything. Use hashing.
You need every pair, not one answer. Output size already forces O(n²).
The input is a stream you cannot index. Use a window or a heap.

Alternatives that also work: a hash map (O(n) time, O(n) space, any order), and a sort plus binary search for each element (O(n log n)).

When to reach for it

Spot it in the problem0 of 3

Tap the signals you can see in the problem.

Remembersortedpair or tripletin placemirror image

Pick your variant

Opposite ends
Which pointer movesthe end that can't be in the answer
pair sumpalindrome
Read/write
Which pointer movesread always, write when a value is kept
remove duplicates
One per input
Which pointer movesthe one just used
merge sorted arrays

Quick checkWhich problem is a two-pointer fit?

The core idea: every step discards something

Picture a sorted row of numbers with one finger on each end. Add the two numbers you touch.

Opposite ends: find a pair with a target sum

nums (6)

▲ left

▲ right

target: 10
left: 0
right: 5

The array is sorted. Put left on the smallest value (index 0) and right on the largest (index 5).

function pairSum(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++;
    else right--;
  }
  return [-1, -1];
}

All steps as text

The array is sorted. Put left on the smallest value (index 0) and right on the largest (index 5).
nums[0] + nums[5] = 1 + 11 = 12.
12 is too big. 11 plus even the smallest remaining value is too big, so 11 can't be in any pair: move right left.
nums[0] + nums[4] = 1 + 8 = 9.
9 is too small. 1 plus even the largest remaining value is too small, so 1 can't be in any pair: move left right.
nums[1] + nums[4] = 3 + 8 = 11.
11 is too big. 8 plus even the smallest remaining value is too big, so 8 can't be in any pair: move right left.
nums[1] + nums[3] = 3 + 6 = 9.
9 is too small. 3 plus even the largest remaining value is too small, so 3 can't be in any pair: move left right.
nums[2] + nums[3] = 4 + 6 = 10.
10 equals the target, so return [2, 3]. We checked 5 pairs instead of all 15.

Quick checkSorted array, pair sum too big. Which pointer moves?

Play with it

Watch the pattern squeeze the pair, then switch to You play. The lab flags every move you can't justify.

Step by step

Decide what each pointer means
Your invariant: "everything outside left..right is ruled out".
Pick the starting positions
Opposite ends: 0 and n - 1.
Choose which pointer moves, and prove it
Say which element each case rules out.
Handle a match
Record it, then move a pointer.
Stop when the pointers meet
Pairs need two indices: while (left < right).

Template 1: opposite ends

For sorted or symmetric input. Need the original indices of unsorted input? Use a hash map (Hash Maps and Sets).

Only the body changes for palindromes (compare the two ends) and Container With Most Water (move the shorter wall).

// Template 1: opposite ends. Works when the input is sorted (or symmetric, like a palindrome):
// the sum or comparison at the two ends tells you which end can never be part of the answer.
export function pairSum(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;   // nums[left] is too small for every remaining partner
    else right--;               // nums[right] is too big for every remaining partner
  }
  return [-1, -1];
}

Quick checkWhat is the time cost of the opposite-ends template?

Template 2: read and write pointers

read visits every element; write marks where the next kept one goes.

Same direction: read and write pointers

nums (7)

▲ write

write: 1

nums[0] is always unique, so the unique prefix (the shaded band) starts as just index 0, and write points at the next free slot.

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) {
      nums[write] = nums[read];
      write++;
    }
  }
  return write;
}

All steps as text

nums[0] is always unique, so the unique prefix (the shaded band) starts as just index 0, and write points at the next free slot.
nums[1] = 1 equals the last unique value: a duplicate. Skip it; write stays at 1.
nums[2] = 2 differs from the last unique value 1: it's new.
Copy 2 into the next free slot, index 1.
Move write to 2. The unique prefix is now 1, 2.
nums[3] = 3 differs from the last unique value 2: it's new.
Copy 3 into the next free slot, index 2.
Move write to 3. The unique prefix is now 1, 2, 3.
nums[4] = 3 equals the last unique value: a duplicate. Skip it; write stays at 3.
nums[5] = 3 equals the last unique value: a duplicate. Skip it; write stays at 3.
nums[6] = 4 differs from the last unique value 3: it's new.
Copy 4 into the next free slot, index 3.
Move write to 4. The unique prefix is now 1, 2, 3, 4.
read has scanned everything. The first 4 slots hold the unique values; whatever is after them doesn't matter. Return 4.

// Template 2: same direction. `read` visits every element; `write` marks the end of the part you keep.
// Everything before `write` is final, so the array is compacted in place with O(1) extra space.
export function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) {   // a value we haven't kept yet
      nums[write] = nums[read];
      write++;
    }
  }
  return write;                             // length of the unique prefix
}

Quick checkIn read and write pointers, which one runs ahead?

Template 3: one pointer per input

Two sorted sequences? Give each a pointer and take the side that comes next.

Two inputs, one output: fill from the back

nums (5)

-4

-1

▲ left

▲ right

out (5)

▲ pos

left: 0
right: 4

Squares of negatives can be large, so the biggest square is at one of the two ends. Fill the output from the back.

function sortedSquares(nums) {
  const out = new Array(nums.length);
  let left = 0, right = nums.length - 1;
  for (let pos = nums.length - 1; pos >= 0; pos--) {
    const a = nums[left] ** 2, b = nums[right] ** 2;
    if (a > b) { out[pos] = a; left++; }
    else { out[pos] = b; right--; }
  }
  return out;
}

All steps as text

Squares of negatives can be large, so the biggest square is at one of the two ends. Fill the output from the back.
Compare the squares at the ends: -4² = 16 and 10² = 100.
100 is at least as large: write it at out[4] and move right inward.
Compare the squares at the ends: -4² = 16 and 3² = 9.
16 is larger: write it at out[3] and move left inward.
Compare the squares at the ends: -1² = 1 and 3² = 9.
9 is at least as large: write it at out[2] and move right inward.
Compare the squares at the ends: -1² = 1 and 0² = 0.
1 is larger: write it at out[1] and move left inward.
Compare the squares at the ends: 0² = 0 and 0² = 0.
0 is at least as large: write it at out[0] and move right inward.
Every slot is filled, largest first from the back, so out is sorted. One pass, O(n).

// Template 3: one pointer per input (or both ends of one input) feeding an output.
// The largest square of a sorted array sits at one of its two ends, so fill the result from the back.
export function sortedSquares(nums) {
  const out = new Array(nums.length);
  let left = 0;
  let right = nums.length - 1;
  for (let pos = nums.length - 1; pos >= 0; pos--) {
    const a = nums[left] ** 2;
    const b = nums[right] ** 2;
    if (a > b) {
      out[pos] = a;
      left++;
    } else {
      out[pos] = b;
      right--;
    }
  }
  return out;
}

// The same shape merges two sorted arrays: compare the heads, take the smaller, advance that pointer.
export function mergeSorted(a, b) {
  const out = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  while (i < a.length) out.push(a[i++]);
  while (j < b.length) out.push(b[j++]);
  return out;
}

Quick checkMerging two sorted arrays: how many pointers?

Try it

try-it.js

// Edit the inputs and press Run. pairSum and removeDuplicates are the templates above.
console.log(pairSum([1, 3, 4, 6, 8, 11], 10));   // [2, 3]
console.log(pairSum([2, 4, 5, 9], 12));          // [-1, -1]

const nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
const k = removeDuplicates(nums);
console.log(k, nums.slice(0, k));                // 5 [0, 1, 2, 3, 4]

Complexity

Variant	Time	Extra space
Opposite ends, sorted input	O(n)	O(1)
Read/write compaction	O(n)	O(1)
3Sum: fix one, then opposite ends	O(n²)	O(1)
Merge two sorted inputs	O(n + m)	O(n + m)

JavaScript you'll use

JavaScript refresher: Sorting and comparators Destructuring, spread and rest Arrays: create, read, update

Universal problem-solving framework

Use the same thirteen steps on every problem. They stop you from typing code before you know why it works.

#	Step	Why it matters
1	Restate the input and output. Ask: sorted? duplicates? indexes or values?	A wrong assumption ruins every later step.
2	Read the limits. `n` up to 100,000 means O(n log n) or better.	Tells you O(n²) will time out.
3	Write the brute force: try every pair.	A correct slow answer is your test oracle.
4	Find the repeated work.	Most pairs can never win. Name why.
5	Find the invariant: what is true outside `left..right`?	Without it, a pointer move is a guess.
6	Pick the shape: opposite ends, read/write, or one per input.	The shape fixes the starting points.
7	Pick the data structure. Usually just the array and two integers.	Keeps space at O(1).
8	Write the move rule as "if X, drop Y because Z".	The `because` is the proof.
9	Dry-run a small example by hand.	Catches off-by-one before you type.
10	Write the code in JavaScript.	Small and readable beats clever.
11	Test: empty, one item, duplicates, negatives, all equal.	Pointers break at the edges.
12	State time and space, and name the sort if there is one.	Interviewers always ask.
13	Explain it aloud in four sentences.	Shows you understand it, not just recall it.

The framework on Container With Most Water

You get heights. Pick two lines. Area is width * min(height). Find the biggest area.

Clarify. The output is one number, not indexes. Heights are not negative.
Limits. n up to 100,000. O(n²) is about 5 billion checks, so aim for O(n).
Brute force. Try every pair, keep the best. O(n²) time, O(1) space.
Repeated work. Start with the widest pair, indexes 0 and n - 1. Every other pair is narrower.
Invariant. The best container is always inside left..right.
Shape. Opposite ends.
Data. Two integers and best.
Move rule. Drop the shorter wall, because any container that keeps it is narrower and no taller.
Dry run. Heights [1, 8, 6, 2, 5, 4, 8, 3, 7] give a best area of 49, between indexes 1 and 8.
Steps 10 to 13. The code, tests, cost and the spoken answer are in the worked problems below.

Pattern catalog and problem archetypes

Six archetypes cover almost every two-pointer interview problem.

1. Opposite ends with a target

Idea. Compare the two ends. The comparison tells you which end to drop.
Signals. Sorted input, a pair or triplet, "closest to", "at most".
Template. while (left < right): compute, then left++ or right--.
Variations. Count pairs (count += right - left), closest sum, unique pairs.
Traps. Unsorted input. Recording a match without moving a pointer.
Cost. O(n) time, O(1) space.
Connects to. Binary search shrinks one range. This shrinks two ends.

2. Mirror comparison

Idea. A palindrome reads the same from both ends.
Signals. "Palindrome", "symmetric", "reverse".
Template. Skip what does not count, compare the two ends, move both.
Traps. Guard each skip loop with left < right. Case and punctuation.
Cost. O(n) time, O(1) space.

3. Read and write pointers

Idea. read scans everything. write marks the end of what you keep.
Signals. "In place", "remove", "move to the end", O(1) space.
Template. for (read...): if you keep it, copy to write, then write++.
Variations. Remove duplicates, move zeroes, remove one value, partition.
Traps. splice inside the loop skips items and costs O(n) per call.
Cost. O(n) time, O(1) space.
Connects to. Sliding window also uses two pointers that move the same way.

4. One pointer per input

Idea. With two sorted inputs, the next output is at one of the two heads.
Signals. "Merge", "intersection", "is subsequence".
Template. Compare heads, take one, advance it, then drain what is left.
Traps. Forgetting the leftover tail. Wrong < or <= when equal values matter.
Cost. O(n + m) time. O(n + m) space if you build a new output.

5. Fix one, then walk two (k-sum)

Idea. Turn 3Sum into n pair-sum problems: fix nums[i], then run opposite ends on the rest.
Signals. "Triplet", "four numbers", "no duplicates".
Template. Sort. For each i, skip a repeated value, then walk i + 1..n - 1.
Traps. Duplicate handling. Comparing with the wrong neighbour.
Cost. O(n²) for 3Sum, O(n³) for 4Sum. O(1) extra space, not counting the output.

6. Three-way partition and settle-the-smaller-side

Idea. Keep extra state so one side is settled each step: low, mid, high for sorting 0, 1 and 2, or leftMax and rightMax for rain water.
Signals. Very few distinct values, or a "the smaller side decides" argument.
Traps. Do not advance mid after swapping with high. The swapped-in value is unchecked.
Cost. O(n) time, O(1) space.

Combining patterns. Sort plus two pointers gives 3Sum. Two pointers plus a running maximum gives Trapping Rain Water. Add a hash map when you also need indexes. If the question is "how many subarrays", move on to prefix sums.

Worked problems: easy to hard

Each problem has the same parts: statement, example, assumptions, brute force, insight, steps, code, dry run, cost, edge cases, alternatives, follow-ups.

Beginner: reverse an array in place

Statement. Reverse arr without making a second array.
Example. [1, 2, 3, 4] becomes [4, 3, 2, 1].
Assumptions. You may change the input. It can be empty.
Brute force. Copy it backwards into a new array. O(n) time, O(n) space, and it breaks the in-place rule.
Insight. Swap the first and last items, then the second and second-to-last. Work inward until the pointers meet.

Dry run. [1, 2, 3, 4]: swap indexes 0 and 3 to get [4, 2, 3, 1]. Swap 1 and 2 to get [4, 3, 2, 1]. Now left is 2 and right is 1, so stop.
Cost. O(n) time, O(1) space.
Edge cases. [] and [7] skip the loop. An odd length leaves the middle item alone.
Follow-up. Rotate an array by k: reverse all of it, then reverse each of the two parts.

function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {                        // stop when they meet: a middle item stays put
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

i	nums[i]	Walk	Found
0	-4	sums -3, -3, -2, -1: never reaches 0	none
1	-1	`(-1, 2)` sums to 0, then `(0, 1)` sums to 0	`[-1, -1, 2]`, `[-1, 0, 1]`
2	-1	same value as `i = 1`	skipped
3	0	`1 + 2 = 3`, then the pointers meet	none

Medium: Container With Most Water (prove the move)

Container With Most WaterMedium

left	right	area	best	Move
0 (1)	8 (7)	8	8	left is shorter: `left++`
1 (8)	8 (7)	49	49	right is shorter: `right--`
1 (8)	7 (3)	18	49	`right--`
1 (8)	6 (8)	40	49	tie, either move is safe: `right--`

Hard: Trapping Rain Water (settle the smaller side)

Trapping Rain WaterHard

left	right	leftMax	rightMax	Settle	Water
0	4	3	4	left: 3 - 3 = 0	0
1	4	3	4	left: 3 - 0 = 3	3
2	4	3	4	left: 3 - 2 = 1	4
3	4	3	4	left: 3 - 0 = 3	7
4	4	4	4	right: 4 - 4 = 0	7

Deriving the complexity

Do not memorise "two pointers is O(n)". Count the moves.

Case	Opposite ends	Read and write
Best	O(1) if the first pair matches	O(n), you still scan everything
Worst	O(n)	O(n)
Guarantee	Worst case, no hashing involved	Worst case

Common mistakes and debugging

Each mistake has a symptom to look for.

1. Using it on unsorted input

Why. The "drop an end" proof needs order.
Fails. pairSum([1, 9, 2, 3], 5) returns [-1, -1], but 2 + 3 = 5.
Spot it. The answer is "none" when you can see one.
Fix. Sort first, or use a hash map if you need the original indexes.

2. Forgetting to move after a match

Why. You record the answer and loop again with the same pointers.
Spot it. The program hangs, or the same triplet repeats forever.
Fix. Every branch of the loop must move at least one pointer. Check this branch by branch.

3. Using `<=` instead of `<` for pairs

Fails. pairBad([3, 4], 6) with while (left <= right) returns [0, 0], because 3 + 3 = 6 uses one item twice.
Fix. Pairs need two different items, so use left < right. Trapping Rain Water is different: its last bar still needs settling, so it uses <=.

4. Sorting numbers without a comparator

Fails. [10, 9, 1].sort() gives [1, 10, 9]. Negatives break too: [-3, -1, 2].sort() gives [-1, -3, 2].
Fix. Always nums.sort((a, b) => a - b).
Related. sort changes the array in place and returns the same array. Copy first ([...nums].sort(...), or toSorted) if the caller's order matters.

5. Skipping duplicates in the wrong place

Fails. Without the checks, [-1, -1, 0, 1, 1] returns [-1, 0, 1] twice. Comparing nums[i] with nums[i + 1] instead of nums[i - 1] drops [-1, -1, 2].
Fix. Skip a repeated i only when it equals the previous value, and skip copies after recording a match.

6. Running off the end in a skip loop

Fails. In Valid Palindrome, while (!isAlnum(s[left])) left++ on ".," runs past the end. s[left] is undefined and the next line throws a TypeError.
Fix. Put left < right in every inner while.

7. Read and write bugs

Fails. splice in the loop turns [0, 0, 1] into [0, 1] and costs O(n) per call. Overwriting without swapping turns [0, 1, 0, 3] into [1, 3, 0, 3] and leaves stale values at the end.
Fix. Swap, or fill the tail with zeroes after the loop.

Boundary checklist

Empty array. One item. Two items. All equal. Duplicates at the ends. Negatives. All positive. Already sorted. Reverse sorted.

JavaScript note: strings are indexed by UTF-16 code units, so "😀".length is 2 and [..."😀"].length is 1. Two pointers on raw indexes can split an emoji. Spread to an array first if the input may contain them.

Pattern	Pointer movement	Needs	Time	Space	Choose it when
Two pointers, opposite ends	Inward from both ends	Sorted or symmetric input	O(n)	O(1)	A comparison tells you which end to drop
Hash map	None	Nothing	O(n) expected	O(n)	Unsorted data, or you need original indexes
Sliding window	Same direction, range between	A contiguous range with a rule	O(n)	O(1) to O(k)	"Longest" or "shortest" subarray or substring
Binary search	`lo` and `hi` halve the range	Monotonic condition	O(log n)	O(1)	One target or boundary in sorted data
Fast and slow	Same direction, two speeds	A linked list or a sequence	O(n)	O(1)	Cycles, middle of a list
Prefix sums	None	Fixed array	O(n) build, O(1) query	O(n)	Many range queries, or negatives with a subarray target

Practice roadmap

Do the problems in order inside each stage.

1. Foundation

Problem	Level	Practises	Discover this	Hint
Valid PalindromeEasy	Easy	Mirror comparison	Skipping junk without a copy	Where do the two ends start?
Move ZeroesEasy	Easy	Read and write	Everything before `write` is final	What should be true about the left part after each step?
Remove Duplicates from Sorted Array	Easy	Read and write	Compare with the last kept value	What do you compare `read` against?

2. Pattern recognition

Problem	Level	Practises	Discover this	Hint
Two Sum on a Sorted ArrayMedium	Medium	Opposite ends	Order lets you drop an end	If the sum is too big, which value is useless?
Squares of a Sorted Array	Easy	One per input, from the back	The biggest square is at an end	Where can the largest result come from?
Is Subsequence	Easy	One per input	One pointer moves only on a match	Which pointer must always move?
Merge Sorted Array	Easy	One per input	Fill from the back	What goes wrong if you fill from the front?

3. Optimisation

Problem	Level	Practises	Discover this	Hint
3SumMedium	Medium	Fix one, walk two	Reduce to pair sum, then dedupe	After sorting, where do equal values sit?
Container With Most WaterMedium	Medium	Prove the move	Width only shrinks, so height must grow	Which wall limits the height?
Rotate ArrayMedium	Medium	In place	Reverse three times	What does reversing do to the order of two blocks?
Sort Colors	Medium	Three pointers	An unchecked value arrives after one swap	After swapping with `high`, is `mid` done?

4. Mixed patterns

Problem	Level	Practises	Discover this	Hint
3Sum Closest	Medium	Sort, fix one, walk two	Track the nearest sum, not a match	What do you update on every pass?
4Sum	Medium	Nested fix, then walk two	Dedupe at two levels	How many loops sit outside the walk?
Trapping Rain WaterHard	Hard	Settle the smaller side	The smaller max decides the water	Which side's max can you trust right now?

5. Interview-level revision

Redo these cold, out loud, with a timer. Aim for under 20 minutes each, including tests.

3SumMedium
Container With Most WaterMedium
Trapping Rain WaterHard
Valid Palindrome II: the palindrome walk plus one allowed deletion.

Active recall and interview readiness

Try every part before you open an answer. Struggling helps you remember.

Revision sheet

Idea. Each pointer move rules out an element for good.
Three shapes. Opposite ends, read and write, one per input.
Invariant. Everything outside left..right is decided.
Cost. O(n) after sorting. O(n log n) with the sort. 3Sum is O(n²). Space is O(1).
Must-do habits. Numeric comparator. Move after every match. left < right in every inner loop. Skip duplicates after recording.
Switch to a hash map when the input is unsorted and you need indexes.
Switch to prefix sums when the question counts subarrays and values can be negative.

Decision tree

Flashcards

What must be true for opposite-ends pair search to work?

The input is sorted, so a comparison tells you which end can never be part of the answer.

What do read and write mean?

read scans every item. write is where the next kept item goes. Everything before write is final.

Why is dropping the shorter wall safe in Container With Most Water?

Any container that keeps it is narrower and no taller, so it can never beat the current one.

Why does 3Sum skip a repeated `i`?

The same first value would find the same triplets again.

Why must the inner skip loops check `left < right`?

Without it they can run off the end, and s[left] becomes undefined.

When do you use `<=` in the loop condition?

When the last bar still needs a decision, as in Trapping Rain Water. Pair search needs two different items, so it uses <.

Can I sort the input, or is it already sorted? Or is it symmetric?
|
+-- no  --> Do I need to remember what I have seen?
|             yes: hash map
|
+-- yes --> What must I produce?
              a pair or triplet with a target      --> opposite ends (k-sum: fix one first)
              the same array, rewritten in place   --> read and write
              one merged or filtered output        --> one pointer per input
              a growing and shrinking range        --> sliding window, not this page
              a bottleneck of two sides            --> settle the smaller side

Trace the code

Work out each answer on paper, then check the key below.

Concept quiz

A pair-sum walk on a sorted array finds nums[left] + nums[right] > target. Which pointer moves, and why?
Why can opposite-ends pair search not return the original indexes after a sort?
In Container With Most Water, the two walls are equal. Does it matter which pointer moves?
Why does 3Sum stay O(n²) even though it sorts?
You must remove all copies of a value from an array in place. Which shape fits, and why not splice?

Problems to try without solutions

Two Sum II. nums is sorted. Return the 1-based indexes of the pair that sums to target. Use O(1) space.
Count the pairs. Given a sorted array and target, count pairs with nums[i] + nums[j] < target. Aim for O(n).
Merge two sorted arrays into a new array, then do it in place when the first array has spare room at the end.
Remove Element. Remove every copy of val in place and return the new length.
Dutch flag. Sort an array of 0s, 1s and 2s in one pass, with no counting.
Longest palindrome by deletion. Check whether a string can become a palindrome by deleting at most one character.

Mock interview: "Closest pair to a target"

Say it out loud as if the interviewer were in the room. Open a hint only when you are stuck.

You get a sorted array of integers and a number target. Return the two values whose sum is closest to target.

Self-assessment checklist

I can say, in one sentence, why each pointer move is safe.
I can write opposite ends, read and write, and merge from memory.
I always write the brute force first and can state its cost.
I use a numeric comparator without thinking about it.
I can explain why 3Sum is O(n²), not O(n³).
I can choose between two pointers, a hash map and a sliding window for a new problem.
I test empty, one item, duplicates and negatives before I say "done".

Answer key

Read this only after you have tried the questions.

Trace the code.

2 3. The walk goes 1 + 11 (too big, right--), 1 + 8 (too small, left++), 3 + 8 (too big), 3 + 6 (too small), then 4 + 6 = 10 at indexes 2 and 3.
[1, 10, 9]. With no comparator, numbers sort as strings.
2 [1, 3, 0, 3]. This overwrites without swapping, so the old tail values stay behind. Only the first write items are meaningful.
[0, 0]. With l <= r, the loop allows l === r, so 3 + 3 = 6 counts one item twice.

Concept quiz.

right moves left. The right value is the largest still in play. If the sum is too big even with the smallest partner, it fits no pair.
Sorting moves values to new positions, so the old indexes are gone. Sort [value, index] pairs, or use a hash map.
No. Both walls have the same cap, so either one can be dropped without losing a better container.
The sort costs O(n log n), and the walk costs O(n) for each of n values of i. O(n²) is bigger, so it wins.
Read and write: copy each item that is not val to write. splice shifts the whole tail on every call, so it is O(n²), and it skips the item that slides into the freed slot.

Hint 1: what is the slow answer?

Try every pair and keep the smallest Math.abs(sum - target). That is O(n²).

Hint 2: what does the sort give you?

If the sum is below target, the left value is too small for every remaining partner. If it is above, the right value is too big. Same move rule as pair sum.

Hint 3: what changes from exact pair sum?

There may be no exact match. Do not return early. On every pass, compare the gap with the best gap so far and keep the better pair. Stop when the pointers meet.

Hint 4: edge cases to raise yourself

Fewer than two items. Two items. A tie between two pairs. Negative numbers and an Infinity start value for the best gap.

A strong answer sounds like this

The array is sorted, so I use two pointers from the ends. I compare the sum with the target, track the closest pair so far, and move the left pointer if the sum is too small or the right pointer if it is too big. Each move rules out a value for good, so it is O(n) time and O(1) space.

// Q1
const nums = [1, 3, 4, 6, 8, 11];
let left = 0;
let right = nums.length - 1;
while (left < right) {
  const sum = nums[left] + nums[right];
  if (sum === 10) break;
  if (sum < 10) left++;
  else right--;
}
console.log(left, right);

// Q2
console.log([10, 9, 1].sort());

// Q3
const a = [0, 1, 0, 3];
let write = 0;
for (let read = 0; read < a.length; read++) {
  if (a[read] !== 0) a[write++] = a[read];
}
console.log(write, a);

// Q4
function pairBad(nums, target) {
  let l = 0;
  let r = nums.length - 1;
  while (l <= r) {
    const s = nums[l] + nums[r];
    if (s === target) return [l, r];
    if (s < target) l++;
    else r--;
  }
  return [-1, -1];
}
console.log(pairBad([3, 4], 6));

What to study next

Two pointers that move the same way and keep a rule true for the range between them are a sliding window.

Interview questions

Two Sum on an unsorted array: two pointers or a hash map?

A hash map: one pass, and it keeps indices. Two pointers wins on sorted input or when O(1) space is required.

How do you extend 3Sum to 4Sum?

Fix numbers with nested loops until two remain, then walk the ends.

Why is moving the shorter wall safe in Container With Most Water?

Any container keeping the shorter wall is narrower and no taller, so that wall is ruled out.

When does two pointers not apply?

When no move safely discards anything, like an unsorted sum target. Use hashing instead.

Check yourself

Question 1 of 3

Score 2 out of 3 or better to mark this page complete.

1. In a sorted array, nums[left] + nums[right] is smaller than the target. Why is it safe to move left forward?Because the array might contain duplicatesBecause nums[left] plus any value at or before right is too small, so nums[left] can't be in any answerBecause moving right would skip the answer

Practice problems

Solve these in the browser editor. Each runs against hidden tests; the step-by-step solution unlocks after a wrong submission.

Open these in the problem list →

Next: Two pointers that move in the same direction and track the range between them form a sliding window.

Trade-offs

Bring it up before they ask

Roadmap and prerequisites

Where it fits

Prerequisites

Why this pattern exists

How it connects to other patterns

Learning sequence

Recognition guide: when to use it, and when not to

Strong signals

Misleading signals

Choosing between the three shapes

When to avoid it

When to reach for it

The core idea: every step discards something

Opposite ends: find a pair with a target sum

Play with it

Squeeze the pair

Step by step

Decide what each pointer means

Pick the starting positions

Choose which pointer moves, and prove it

Handle a match

Stop when the pointers meet

Template 1: opposite ends

Template 2: read and write pointers

Same direction: read and write pointers

Template 3: one pointer per input

Two inputs, one output: fill from the back

Try it

Complexity

JavaScript you'll use

Universal problem-solving framework

The framework on Container With Most Water

Pattern catalog and problem archetypes

1. Opposite ends with a target

2. Mirror comparison

3. Read and write pointers

4. One pointer per input

5. Fix one, then walk two (k-sum)

6. Three-way partition and settle-the-smaller-side

Worked problems: easy to hard

Beginner: reverse an array in place

Easy: Valid Palindrome

Easy: Move Zeroes (read and write)

Medium: 3Sum (fix one, then walk two)

Medium: Container With Most Water (prove the move)

Hard: Trapping Rain Water (settle the smaller side)

Deriving the complexity

Common mistakes and debugging

1. Using it on unsorted input

2. Forgetting to move after a match

3. Using <= instead of < for pairs

4. Sorting numbers without a comparator

5. Skipping duplicates in the wrong place

6. Running off the end in a skip loop

7. Read and write bugs

Boundary checklist

Comparison with related patterns

Practice roadmap

1. Foundation

2. Pattern recognition

3. Optimisation

4. Mixed patterns

5. Interview-level revision

Active recall and interview readiness

Revision sheet

Decision tree

Flashcards

Trace the code

Concept quiz

Problems to try without solutions

Mock interview: "Closest pair to a target"

Self-assessment checklist

Answer key

What to study next

Interview questions

Check yourself

Practice problems

3. Using `<=` instead of `<` for pairs