Index your code with Devin
DeepWiki

doocs/leetcode

Menu

Two Pointers Pattern

Relevant source files

Purpose and Scope

This document explains the Two Pointers Pattern, a fundamental algorithmic technique implemented across problems in the solution/ directory. The pattern uses two index variables that traverse an array or sequence in a coordinated manner to solve problems in linear time. This page focuses on the two main variants: same-direction pointers (fast-slow) and opposite-direction pointers (left-right).

For other array manipulation patterns, see Hash Table Pattern, Sliding Window Pattern, and Binary Search Pattern. For non-array algorithmic patterns, see DFS and Backtracking Pattern.

Pattern Overview

The two pointers technique optimizes array traversal by maintaining two index positions that move according to problem-specific rules. This eliminates the need for nested loops or additional data structures in many scenarios.

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/README.md1-96 solution/0000-0099/0027.Remove Element/README.md1-96 solution/0200-0299/0283.Move Zeroes/README.md1-68 solution/0000-0099/0080.Remove Duplicates from Sorted Array II/README.md1-99 solution/0000-0099/0011.Container With Most Water/README.md1-74 solution/0000-0099/0015.3Sum/README.md1-93

Same-Direction Two Pointers (Fast-Slow)

Concept

This variant uses two pointers that traverse the array in the same direction, typically from left to right. One pointer (k) tracks the position where the next valid element should be written, while the other pointer (i) scans through the array.

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/README.md76-85 solution/0000-0099/0027.Remove Element/README.md83-92

Core Algorithm Structure

The general pattern follows this structure:

  1. Initialize write pointer k = 0
  2. Iterate through array with scan pointer (for loop or enumerate)
  3. For each element, check condition
  4. If condition met: write element at k, increment k
  5. Return k (length of processed array)

Time Complexity: $O(n)$ - single pass through array
Space Complexity: $O(1)$ - in-place modification

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/README.md78-85

Implementation: Remove Element (Problem 27)

The simplest same-direction pattern removes all occurrences of a target value.

LanguageImplementation File
Pythonsolution/0000-0099/0027.Remove Element/Solution.py1-9
Javasolution/0000-0099/0027.Remove Element/Solution.java1-10
C++solution/0000-0099/0027.Remove Element/Solution.cpp1-11
Gosolution/0000-0099/0027.Remove Element/Solution.go1-10

Algorithm:

  • Variable k tracks count of non-target elements
  • For each element x: if x != val, write x at position k and increment k
  • Elements beyond k are ignored (not returned)

Sources: solution/0000-0099/0027.Remove Element/README.md83-92 solution/0000-0099/0027.Remove Element/Solution.py1-9 solution/0000-0099/0027.Remove Element/Solution.java1-10

Implementation: Move Zeroes (Problem 283)

Moves all zeros to the end while maintaining relative order of non-zero elements.

Key Difference from Remove Element: Uses swap instead of simple assignment to preserve array elements.

Sources: solution/0200-0299/0283.Move Zeroes/README.md58-67 solution/0200-0299/0283.Move Zeroes/Solution.py1-8 solution/0200-0299/0283.Move Zeroes/Solution.java1-12

Implementation: Remove Duplicates from Sorted Array (Problem 26)

Removes duplicates from a sorted array, keeping only unique elements.

Key Condition: k == 0 or x != nums[k - 1]

  • First element always kept (k == 0)
  • Subsequent elements kept only if different from last kept element (nums[k-1])

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/README.md76-85 solution/0000-0099/0026.Remove Duplicates from Sorted Array/Solution.py1-9

Generalization: Keep At Most K Duplicates (Problem 80)

Extends Problem 26 to allow at most 2 (or K) occurrences of each element.

Condition Modified: k < 2 or x != nums[k - 2]

  • First 2 elements always kept (k < 2)
  • Element kept if different from element at position k-2
ProblemConditionMax Occurrences
Problem 26k == 0 or x != nums[k-1]1
Problem 80k < 2 or x != nums[k-2]2
Generalk < K or x != nums[k-K]K

Sources: solution/0000-0099/0080.Remove Duplicates from Sorted Array II/README.md78-94 solution/0000-0099/0080.Remove Duplicates from Sorted Array II/Solution.py1-9

Code Comparison: Same-Direction Pattern

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/Solution.cpp1-12 solution/0000-0099/0027.Remove Element/Solution.cpp1-11 solution/0000-0099/0080.Remove Duplicates from Sorted Array II/Solution.cpp1-12 solution/0200-0299/0283.Move Zeroes/Solution.cpp1-12

Opposite-Direction Two Pointers (Left-Right)

Concept

This variant uses two pointers starting at opposite ends of the array, moving toward each other based on problem conditions. Typically used on sorted arrays to find pairs, triplets, or optimize area/sum calculations.

Sources: solution/0000-0099/0011.Container With Most Water/README.md62-72 solution/0000-0099/0015.3Sum/README.md73-91

Core Algorithm Structure

  1. Initialize l = 0 (left), r = n - 1 (right)
  2. While l < r:
    • Calculate value based on nums[l] and nums[r]
    • Compare with target or update answer
    • Move pointer based on condition:
      • If value too small: l++
      • If value too large: r--
      • If value matches: process and move both
  3. Return result

Time Complexity: $O(n)$ for single pass
Space Complexity: $O(1)$

Sources: solution/0000-0099/0011.Container With Most Water/README.md64-72

Implementation: Container With Most Water (Problem 11)

Finds two lines that form a container with maximum water capacity.

Key Insight: Always move the pointer with the shorter height, as moving the taller one cannot improve the result (width decreases and height is still limited by the shorter line).

FileLines
Pythonsolution/0000-0099/0011.Container With Most Water/Solution.py1-13
Javasolution/0000-0099/0011.Container With Most Water/Solution.java1-16
C++solution/0000-0099/0011.Container With Most Water/Solution.cpp1-18
Gosolution/0000-0099/0011.Container With Most Water/Solution.go1-13

Sources: solution/0000-0099/0011.Container With Most Water/README.md62-72 solution/0000-0099/0011.Container With Most Water/Solution.py1-13

Implementation: 3Sum (Problem 15)

Finds all unique triplets that sum to zero. Combines sorting with opposite-direction two pointers.

Algorithm Structure:

  1. Sort array: nums.sort()
  2. Outer loop: fix first element nums[i] (index i from 0 to n-3)
  3. Inner two pointers: find pairs nums[j] + nums[k] = -nums[i]
  4. Skip duplicates at all three positions

Duplicate Handling:

  • Skip nums[i] if same as nums[i-1] (line check in outer loop)
  • After finding valid triplet, skip duplicate j and k values in inner loop
LanguageImplementation
Pythonsolution/0000-0099/0015.3Sum/Solution.py1-26
Javasolution/0000-0099/0015.3Sum/Solution.java1-29
C++solution/0000-0099/0015.3Sum/Solution.cpp1-30
Gosolution/0000-0099/0015.3Sum/Solution.go1-28
TypeScriptsolution/0000-0099/0015.3Sum/Solution.ts1-29
Rustsolution/0000-0099/0015.3Sum/Solution.rs1-41

Time Complexity: $O(n^2)$ - $O(n \log n)$ for sorting + $O(n)$ for outer loop × $O(n)$ for two pointers
Space Complexity: $O(\log n)$ for sorting (depends on sort implementation)

Sources: solution/0000-0099/0015.3Sum/README.md73-93 solution/0000-0099/0015.3Sum/Solution.py1-26 solution/0000-0099/0015.3Sum/Solution.java1-29

Pattern Recognition and Selection

When to Use Same-Direction Two Pointers

CharacteristicsExample Problems
In-place array modification requiredProblem 26, 27, 80, 283
Maintain relative orderProblem 283 (Move Zeroes)
Process array elements based on conditionProblem 27 (Remove Element)
Remove duplicates from sorted arrayProblem 26, 80
Linear time, constant space requirementAll same-direction problems

When to Use Opposite-Direction Two Pointers

CharacteristicsExample Problems
Sorted array (or can be sorted)Problem 15 (3Sum)
Find pairs/triplets with target sumProblem 15
Optimize area/volume calculationsProblem 11 (Container)
Compare values from both endsProblem 11
Need to explore all combinations efficientlyProblem 15

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/README_EN.md76-97 solution/0000-0099/0015.3Sum/README_EN.md69-89

Multi-Language Implementation Consistency

All two pointers solutions maintain consistent logic across 10+ programming languages. The core algorithm remains identical, with only syntax differences.

Language-Specific Patterns

Python: Uses enumerate for index+value, list comprehensions

Java/C++: Enhanced for-loop or traditional index loop

Go: Range iteration with multiple return values

Rust: Explicit bounds checking and ownership

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/Solution.py1-9 solution/0000-0099/0026.Remove Duplicates from Sorted Array/Solution.java1-10 solution/0000-0099/0026.Remove Duplicates from Sorted Array/Solution.go1-10 solution/0000-0099/0026.Remove Duplicates from Sorted Array/Solution.rs1-13

Moore Voting Algorithm (Problem 169)

A specialized two-pointer variant (candidate and counter) for finding majority element.

Pattern: Single pass with candidate tracking

  • Counter cnt acts as a balance between candidate matches and non-matches
  • When cnt == 0, select new candidate
  • Guaranteed to find majority if one exists (appears > n/2 times)

Sources: solution/0100-0199/0169.Majority Element/README.md60-73 solution/0100-0199/0169.Majority Element/README_EN.md53-65

Multi-Pointer Extensions

For problems requiring more than two pointers:

  • Three pointers: Used in Problem 15 (3Sum) - one fixed, two moving
  • Four pointers: Can extend to 4Sum or other k-sum problems
  • Sliding window: When pointers define a range (see Sliding Window Pattern)

Complexity Summary

PatternTime ComplexitySpace ComplexityProblem Examples
Same-Direction$O(n)$$O(1)$26, 27, 80, 283
Opposite-Direction$O(n)$$O(1)$11
With Sorting$O(n^2)$ or $O(n \log n)$$O(\log n)$15

Sources: solution/0000-0099/0026.Remove Duplicates from Sorted Array/README.md85 solution/0000-0099/0015.3Sum/README.md93 solution/0000-0099/0011.Container With Most Water/README.md72