Pattern #1 · Arrays & Strings · O(N) Time O(1) Space

Two
Pointers

Walk two pointers toward each other from opposite ends of an array or string, and turn O(N²) brute force into O(N) — no extra space required.

🔤 Valid palindrome 🔢 Pair sum on sorted array 🔁 Reverse in place

Scroll to learn

Story Time

The Hiking Backpack ⛰️🎒

Before writing a single line of code, let's understand the intuition through a story.

🎒

Mia Packs for a Hike

Mia has item weights sorted lightest to heaviest: 2, 7, 11, 15. Her backpack has an exact 9 kg limit, and she wants to find two items whose weights add up to exactly that.

😩

The Exhausting Way

At first Mia tries every pair of items: item 1 with item 2, item 1 with item 3, item 2 with item 3, and so on. For 4 items that's 6 pairs; for 1,000 items it's nearly 500,000. This is O(N²) — brute force, and it completely ignores that her list is already sorted.

🧙

A Friend's Trick

A friend points out: "Since your list is sorted, put one finger on the lightest item and one on the heaviest. Too heavy? Move the heavy finger down. Too light? Move the light finger up. Keep going until they meet."

✗ Brute force: check every pair → O(N²)
✓ Two pointers: converge from both ends → O(N)

📍

Visualising the Convergence

Array [2, 7, 11, 15], target = 9. Left and right pointers step toward each other:

2 + 15

sum = 17 — 17 > 9 → move right in

2 + 11

sum = 13 — 13 > 9 → move right in

2 + 7

sum = 9 — 9 = 9 → found! ✓

🚀

Moral of the story

Sorted (or symmetric) data lets you eliminate half the remaining possibilities with every comparison — no nested loop needed. That turns O(N²) brute force into O(N) two pointers.

Interactive

Pointer Visualizer

Watch left and right pointers converge on [2, 7, 11, 15], target = 9.

Start: L=[0]=2, R=[3]=15. Sum = 17. 17 > 9, so move R left.

active pointer match found L left pointer R right pointer

sum = arr[left] + arr[right] Compute the current sum

sum < target → left++ Need bigger — drop the smaller

sum > target → right-- Need smaller — drop the bigger

Complexity

Three Approaches

Approach	Time	Space	Best for
Nested Loops (Brute)	O(N²)	O(1)	Tiny inputs, clarity
Hash Map	O(N)	O(N)	Unsorted input, single pass
Two Pointers Preferred ✓	O(N)	O(1)	Sorted input, no extra space

Two Pointers needs O(1) extra space — but it requires the input to already be sorted (or symmetric, like a string checked for a palindrome). On unsorted input, a hash map trades O(N) space for not needing to sort first.

TypeScript

Implementation

Pair sum → palindrome check → in-place reversal.

// Two Pointers (opposite direction) — O(N) time, O(1) space
// LeetCode 167 — Two Sum II (input array is sorted)
function twoSum(numbers: number[], target: number): number[] {
  let left = 0, right = numbers.length - 1;

  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) {
      return [left + 1, right + 1]; // LeetCode wants 1-indexed
    } else if (sum < target) {
      left++;   // need a bigger sum — drop the smaller number
    } else {
      right--;  // need a smaller sum — drop the larger number
    }
  }
  return [];
}

// [2, 7, 11, 15], target = 9
console.log(twoSum([2, 7, 11, 15], 9)); // → [1, 2]

// Two Pointers (opposite direction) — O(N) time, O(1) space
// LeetCode 125 — Valid Palindrome. Full debugging journey:
// /learn/dsa/two-pointers/valid-palindrome
function isPalindrome(s: string): boolean {
  const filteredString = s.toLowerCase();
  let i = 0, j = filteredString.length - 1;

  while (i < j) {
    while (/[^a-zA-Z0-9]/.test(filteredString[i])) i++;
    while (/[^a-zA-Z0-9]/.test(filteredString[j])) j--;
    if (filteredString[i] !== filteredString[j]) return false;
    i++;
    j--;
  }
  return true;
}

// "A man, a plan, a canal: Panama"
console.log(isPalindrome("A man, a plan, a canal: Panama")); // → true

// Two Pointers (in-place swap) — O(N) time, O(1) space
// LeetCode 344 — Reverse String
function reverseString(s: string[]): void {
  let left = 0, right = s.length - 1;

  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]]; // swap in place
    left++;
    right--;
  }
}

const letters = ["h", "e", "l", "l", "o"];
reverseString(letters);
console.log(letters); // → ["o", "l", "l", "e", "h"]

Want the full debugging story behind isPalindrome() — five real bugs and how each was found? Read the Valid Palindrome case study.

Comparison

Hash Map vs Two Pointers

🗺️ Hash Map Approach O(N) space

Works on unsorted input Yes — no sort needed

Extra memory O(N) — stores every seen value

Two Sum (unsorted) One pass, store complements

Valid Palindrome Not applicable — needs order

Interviews Good default for unsorted pair-sum

👉👈 Two Pointers O(1) space

Works on unsorted input No — requires sorted/symmetric data

Extra memory O(1) — just two indices

Two Sum (sorted) Converge from both ends

Valid Palindrome Natural fit — compare from both ends

Interviews Expected optimal when input is sorted

Not the same as Fast & Slow Pointers — that pattern moves both pointers in the same direction at different speeds to detect cycles. See Fast and Slow Pointers.

Practice

Solve It Yourself

Click any question to see hints and approach.

B Basic

B1 What is the Two Pointers pattern, and what problem does it solve? ⌄

💡 Hint

Think about what makes nested-loop solutions slow when data is already sorted or symmetric. What redundant comparisons do they make?

✅ Answer

The Two Pointers pattern uses two indices that move through a data structure — usually converging from opposite ends — instead of comparing every possible pair. Because sorted or symmetric data lets you eliminate one whole side with each comparison, it reduces O(N²) brute force to O(N) time, typically O(1) extra space.

B2 Given [1, 3, 4, 7, 10], target = 11, trace twoSum step by step. ⌄

💡 Hint

Start left at index 0, right at the last index. Compare the sum to target and move whichever pointer needs to change.

✅ Answer

left=0(1), right=4(10): sum=11 → match! Answer: [1, 5] (1-indexed). Only one step needed here because the first and last elements already summed to the target.

B3 What is the difference between opposite-direction and same-direction two pointers? ⌄

💡 Hint

One pattern starts at both ends and moves inward. The other starts both pointers at (or near) the same spot and moves them forward at different speeds.

✅ Answer

Opposite-direction (this page): pointers start at the two ends and converge inward — used for palindromes, pair sums, and reversal. Same-direction at different speeds (Fast & Slow Pointers): both start near the beginning and move forward, one faster than the other — used for cycle detection and finding the middle of a linked list.

M Intermediate

M1 LeetCode 125 — Valid Palindrome: is "A man, a plan, a canal: Panama" a palindrome ignoring case and non-alphanumeric characters? ⌄

💡 Hint

Lowercase the string, then converge two pointers from both ends, skipping any non-alphanumeric characters as you go.

✅ Answer

Yes — it's a palindrome. This exact problem has a full worked debugging journey (real bugs found and fixed, not just the final answer) on the case study page.

→ Read the full case study

M2 LeetCode 167 — Two Sum II: given a sorted array [2, 7, 11, 15] and target 9, find the two indices. ⌄

💡 Hint

Left pointer at 0, right pointer at the last index. If the sum is too big, move right down; too small, move left up.

✅ Answer

left=0(2), right=3(15): sum=17>9 → right--. left=0(2), right=2(11): sum=13>9 → right--. left=0(2), right=1(7): sum=9 → match! Answer: [1, 2] (1-indexed).

→ Solve on LeetCode ↗

M3 LeetCode 15 — 3Sum: find all unique triplets in [-1,0,1,2,-1,-4] that sum to 0. ⌄

💡 Hint

Sort the array first. Fix one number, then use two pointers on the remaining sorted subarray to find pairs that sum to its negative. Skip duplicates to avoid repeat triplets.

✅ Answer

Sorted: [-4,-1,-1,0,1,2]. Fixing -4: no pair sums to 4 within range. Fixing -1 (first): two pointers find [-1,0,1] and [-1,2,-1]→ dedup. Fixing 0: [0,1,-1] already found (dedup). Answer: [[-1,-1,2],[-1,0,1]]. This exact problem has a full worked debugging journey (real bugs found and fixed) on the case study page.

→ Read the full case study

H Advanced

H1 LeetCode 11 — Container With Most Water: find the max water area for heights [1,8,6,2,5,4,8,3,7]. ⌄

💡 Hint

Two pointers at both ends. Area = width × min(height[left], height[right]). Always move the pointer at the shorter line inward — moving the taller one can only shrink the width without a compensating height gain.

✅ Answer

49 — achieved between index 1 (height 8) and index 8 (height 7): width=7, min height=7, area=49. Moving the shorter pointer each time guarantees you don't miss the optimal pair while still doing only O(N) work.

→ Solve on LeetCode ↗

H2 LeetCode 42 — Trapping Rain Water: how much water is trapped by heights [0,1,0,2,1,0,1,3,2,1,2,1]? ⌄

💡 Hint

Two pointers from both ends, tracking leftMax and rightMax. Water above index i is min(leftMax, rightMax) − height[i]. Advance whichever side has the smaller max — its bound is already determined.

✅ Answer

6 units trapped. Because the side with the smaller max already has its trapped-water ceiling determined (the other side's max is guaranteed ≥ its own), you can safely resolve it in O(N) time and O(1) space instead of precomputing max arrays.

→ Solve on LeetCode ↗

H3 LeetCode 88 — Merge Sorted Array: merge nums2=[2,5,6] into nums1=[1,2,3,0,0,0] in place. ⌄

💡 Hint

Classic two-pointer merge, but working backwards from the end (where the empty slots are) avoids overwriting values in nums1 you haven't read yet.

✅ Answer

Result: [1,2,2,3,5,6]. Compare from the back: place the larger of nums1[i]/nums2[j] into the last open slot, decrementing pointers. Working backward means you never overwrite an unread nums1 element — a key variant of the pattern.

→ Solve on LeetCode ↗

In the Wild

Real-World Applications

🗄️

Database Engines

Merge Join

SQL engines join two already-sorted tables by walking one pointer per table, advancing whichever side is smaller. A nested-loop join would be O(N × M); merge join is O(N + M).

👉👈 How it fits: Pointer i on table A, pointer j on table B (both sorted on the join key). Advance whichever key is smaller; emit a match when keys are equal.

🧬

Bioinformatics

Reverse-Complement Checks

Checking whether a DNA strand reads the same as its reverse complement (a biologically meaningful palindrome) uses the exact same converging two-pointer scan as LeetCode 125.

👉👈 How it fits: Left pointer from the 5' end, right pointer from the 3' end, comparing each base to the complement of the other in O(N) time.

🔀

Version Control

Diffing Sorted Change Lists

Tools that compare two sorted lists of file paths or commit IDs (e.g. finding a common merge base) walk two pointers forward, advancing whichever list is "behind" — avoiding an O(N × M) comparison.

👉👈 How it fits: Pointer i on list A, pointer j on list B. If A[i] < B[j], advance i; if B[j] < A[i], advance j; if equal, it's a common entry — advance both.

📊

External Merge Sort

Merging Sorted Runs

Databases and big-data pipelines that sort data too large for memory write sorted "runs" to disk, then merge them. Each run gets one pointer, always emitting the smallest current value.

👉👈 How it fits: One pointer per run; at each step, compare the current values across all runs and output (then advance) the smallest — generalizes two pointers to K-way merge.

Quick Reference

Cheat Sheet

The Patterns

Start pointers

left = 0, right = n - 1

Converge

while (left < right)

Skip invalid chars

while (!isValid) left++

Swap in place

[a[l], a[r]] = [a[r], a[l]]

When to Use

✓ Checking if a string/array is a palindrome
✓ Pair sum on a sorted array
✓ Reversing an array or string in place
✓ Merging two sorted arrays
✓ Removing duplicates in place (sorted input)
✓ Container / area maximization problems
✓ Comparing two sorted sequences
✓ 3Sum / 4Sum (fix one, converge the rest)

Pointer Types

Opposite Direction

Start at both ends, converge inward. Palindromes, pair sums, reversal.

Same Direction (different speeds)

See Fast & Slow Pointers — cycle detection, middle of linked list.

Complexity

Time: O(N) — each pointer moves at most N steps total

Space: O(1) — just two indices, no extra structures

Keep Learning

You've mastered Two Pointers 🎉

This pattern powers database joins, diff tools, and merge sort — all in O(N) time with a clean converging loop.

Read the Valid Palindrome Case Study → ← Back to DSA Patterns