Two Pointers on Arrays: An Optimization Tool from O(n²) to O(n)

Table of Contents

Overview Problem Definition Core Principle: Step-by-Step Illustration Detailed Algorithm Steps TypeScript Implementation 1. Two Sum II 2. Reverse String 3. Remove Duplicates from Sorted Array 4. Move Zeroes 5. Merge Two Sorted Arrays 6. Three Sum Engineering Optimization: Define Pointer Invariants First Applications and Limitations Typical applications Limitations Summary

835 words

4 minutes

Two Pointers on Arrays: An Optimization Tool from O(n²) to O(n)

2026-04-26

Algorithms

Two Pointers

/

TypeScript

/

Algorithms

Overview#

Array two pointers uses two indices to simultaneously maintain positional relationships within an array. It often optimizes enumerations that would otherwise require nested loops into a single or a few linear scans.

Prerequisites

Array indices: pointers are essentially index variables

Sorted order: left and right pointers often rely on array sorting

Invariant: clearly define the meaning of the interval between the two pointers

Problem Definition#

Given an array or string, use the relative movement of two pointers to accomplish searching, merging, reversing, deduplication, or in-place modification.

Element	Description
Input	Array, target value, two sorted sequences, or string
Output	Index, modified array length, merged result, or optimal value
Pointer pattern	Left-right pointers, fast-slow pointers, separated pointers
Typical benefit	Reduce O(n²) enumeration to O(n) scanning

Core Principle: Step-by-Step Illustration#

Taking two-sum on a sorted array as an example:

1
nums:   2   7   11   15
2
target: 9
3
        L            R

If nums[left] + nums[right] is too large, move the right pointer left; if too small, move the left pointer right.

The premise for this movement to work is that the array is sorted, so after moving, a batch of impossible answers can be safely eliminated.

Detailed Algorithm Steps#

1
Algorithm: TwoPointers(nums, target)
2
Input: sorted array nums, target target
3
Output: the two positions that satisfy the condition
4

5
1. left ← 0, right ← nums.length - 1
6
2. while left < right:
7
3.     sum ← nums[left] + nums[right]
8
4.     if sum == target, return the answer
9
5.     if sum < target, left ← left + 1
10
6.     else right ← right - 1
11
7. return not found

Complexity analysis:

Pattern	Time complexity	Space complexity	Description
Left-right pointers	O(n)	O(1)	Move from both ends toward the middle
Fast-slow pointers	O(n)	O(1)	Same-direction scanning, often used for in-place modification
Separated pointers	O(m + n)	O(m + n) or O(1)	Merge two sequences
Three-sum	O(n²)	O(1)	Sort, fix one number, then use two pointers

TypeScript Implementation#

1. Two Sum II#

1
function twoSum(numbers: number[], target: number): number[] {
2
  let left = 0;
3
  let right = numbers.length - 1;
4

5
  while (left < right) {
6
    const sum = numbers[left] + numbers[right];
7
    if (sum === target) return [left + 1, right + 1];
8
    if (sum < target) left++;
9
    else right--;
10
  }
11

12
  return [-1, -1];
13
}

2. Reverse String#

1
function reverseString(s: string[]): void {
2
  let left = 0;
3
  let right = s.length - 1;
4

5
  while (left < right) {
6
    [s[left], s[right]] = [s[right], s[left]];
7
    left++;
8
    right--;
9
  }
10
}

3. Remove Duplicates from Sorted Array#

1
function removeDuplicates(nums: number[]): number {
2
  if (nums.length === 0) return 0;
3

4
  let slow = 0;
5
  for (let fast = 1; fast < nums.length; fast++) {
6
    if (nums[fast] !== nums[slow]) {
7
      slow++;
8
      nums[slow] = nums[fast];
9
    }
10
  }
11

12
  return slow + 1;
13
}

4. Move Zeroes#

1
function moveZeroes(nums: number[]): void {
2
  let write = 0;
3

4
  for (let read = 0; read < nums.length; read++) {
5
    if (nums[read] !== 0) {
6
      [nums[write], nums[read]] = [nums[read], nums[write]];
7
      write++;
8
    }
9
  }
10
}

5. Merge Two Sorted Arrays#

1
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
2
  let p1 = m - 1;
3
  let p2 = n - 1;
4
  let tail = m + n - 1;
5

6
  while (p2 >= 0) {
7
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
8
      nums1[tail--] = nums1[p1--];
9
    } else {
10
      nums1[tail--] = nums2[p2--];
11
    }
12
  }
13
}

6. Three Sum#

1
function threeSum(nums: number[]): number[][] {
2
  nums.sort((a, b) => a - b);
3
  const result: number[][] = [];
4

5
  for (let i = 0; i < nums.length - 2; i++) {
6
    if (i > 0 && nums[i] === nums[i - 1]) continue;
7

8
    let left = i + 1;
9
    let right = nums.length - 1;
10

11
    while (left < right) {
12
      const sum = nums[i] + nums[left] + nums[right];
13
      if (sum === 0) {
14
        result.push([nums[i], nums[left], nums[right]]);
15
        while (left < right && nums[left] === nums[left + 1]) left++;
16
        while (left < right && nums[right] === nums[right - 1]) right--;
17
        left++;
18
        right--;
19
      } else if (sum < 0) {
20
        left++;
21
      } else {
22
        right--;
23
      }
24
    }
25
  }
26

27
  return result;
28
}

Engineering Optimization: Define Pointer Invariants First#

Pattern	Invariant	Common use
Left-right pointers	The answer lies within `[left, right]`	Sorted search, palindrome, reversal
Fast-slow pointers	`[0, slow]` is the processed valid interval	Deduplication, filtering, moving elements
Separated pointers	Both inputs advance in sorted order	Merging arrays, merge sort
Front-back write pointers	Tail space has not been overwritten	In-place merging

Don’t just memorize templates for two-pointer code; explain why moving a certain pointer won’t miss the answer.

Applications and Limitations#

Typical applications#

Finding two-sum in a sorted array
In-place deduplication, moving zeroes, removing elements
Palindrome checking, string reversal
Merging sorted arrays, three-sum

Limitations#

Limitation	Description
Often relies on sorted order	Unsorted arrays usually require sorting first or using a hash table
Movement rules need proof	Answers will be missed if candidates cannot be safely eliminated
Sorting changes the input	For problems like three-sum, note whether in-place sorting is allowed

Summary#

Key points:

The value of two pointers is replacing repeated enumeration with linear movement.
Left-right pointers typically rely on sorted order; fast-slow pointers are often used for in-place modification.
Before each pointer movement, you must be able to prove that the skipped states cannot be the answer.
Three-sum is a classic combination of “sort + fix one number + left-right pointers.”