ReviseAlgo Logo

Arrays

Two Pointers Pattern

Master two-pointer techniques—opposite direction, slow-fast read/write, and multi-pointer partitioning—to optimize array problems from O(N²) to O(N).

Last Updated: August 2, 2026 • 25 min read

1. Introduction

What is the Two Pointers Pattern?

The Two Pointers pattern is an algorithmic technique where two index variables iterate through a data structure (typically an array or string) simultaneously.

Why is it Important?

In naive solutions, checking all pairs of elements requires nested loops resulting in O(N²) time complexity. By leveraging array ordering or logical properties, two pointers allow you to eliminate unnecessary comparisons and solve pair/partition problems in linear O(N) time and O(1) auxiliary space.

Where is it Used?

  • Search Engines & Database Joins: Merging two pre-sorted lists or streams efficiently.
  • Data Cleaners & Compression: Removing duplicate records or filtering zero entries in-place.

    • 2. Mental Model

    Imagine two people walking towards each other from opposite ends of a row of ordered numbers trying to find two numbers that sum up to Target = 15.

    1. Calculate Sum: arr[L] + arr[R] = 2 + 16 = 18. 2. Evaluate: 18 is too big! To get a smaller sum, the person on the right takes a step left (R--). 3. Re-evaluate: arr[L] + arr[R] = 2 + 13 = 15. Found the target in 2 steps!

    3. Concept: The Two Main Variants

    Variant 1: Opposite Direction (Converging Pointers)

    Used when array elements are sorted or when working inward from boundaries (e.g., Two Sum Sorted, Palindrome Check, Container With Most Water).
  • left starts at 0, right starts at N - 1.
  • Move left++ to increase sum/value; move right-- to decrease sum/value.

    • Variant 2: Same Direction (Slow & Fast / Write Pointer)

    Used for in-place modification without extra memory (e.g., Remove Duplicates, Move Zeroes).
  • fast pointer scans every element in the array.
  • slow pointer marks the destination slot for valid elements.

    • 4. Visuals

    Two Pointers Convergence Flowchart

    Pattern Recognition Matrix

    Scenario / KeywordPointer StrategyTime ComplexitySpace Complexity
    Sorted Array + Pair SumOpposite direction (L=0, R=N-1)O(N)O(1)
    In-place Remove/FilterSame direction (Slow/Fast)O(N)O(1)
    3Sum / 4SumFix 1 element + Two Pointers on restO(N²)O(1)
    Container With Most WaterMove pointer with smaller heightO(N)O(1)

    5. Real-World Examples

  • Database Merge-Join: SQL query execution engines use two pointers to join two pre-sorted tables on a foreign key in O(N + M) time.
  • In-Place Stream Sanitization: Processing telemetry data streams to filter out noise bytes without creating temporary copy arrays.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers present pair-sum or array manipulation problems and explicitly request: "Can you optimize this to O(N) time without using a HashSet/HashMap for O(1) auxiliary space?"

    Common Mistakes

    Warning: 1. Applying Converging Two Pointers to Unsorted Arrays: Opposite-direction two pointers only work when array values follow a monotonic order (sorted). If unsorted, sort first (O(N log N)) or use a HashMap.
    > 2. Duplicate Triplets in 3Sum: Forgetting to skip identical values (while (nums[L] == nums[L+1]) L++) after finding a valid triplet leading to duplicate results in output lists.

    7. Summary

  • Opposite-Direction Pointers start at opposite ends and move inward based on comparisons—ideal for sorted array pair problems.
  • Same-Direction (Slow/Fast) Pointers move in tandem to filter or modify array elements in-place.
  • Eliminates nested loops, reducing time complexity from O(N²) to O(N) with O(1) extra space.

    • 8. Quiz

    Question 1: Why does the opposite-direction two pointer technique require the array to be sorted? Answer: Sorting provides monotonicity. If arr[L] + arr[R] < target, we know with 100% certainty that incrementing L increases the sum, and decrementing R decreases it. Unsorted arrays provide no such guarantee.
    Question 2: What is the optimal time complexity of 3Sum using Two Pointers? Answer: O(N²). Sorting the array takes O(N log N). The outer loop runs N times, and for each iteration, the inner two-pointer search runs in O(N) time. O(N log N) + O(N²) = O(N²).
    Question 3: In the "Container With Most Water" problem, why do we always advance the pointer with the smaller height? Answer: Water height is limited by the shorter line: Area = \min(h_L, h_R) × (R - L). Moving the taller line can only decrease width without increasing height. Moving the shorter line is the only way to potentially find a larger area.
    Question 4: How does a slow-fast pointer setup remove zeroes from an array in-place? Answer: fast scans every element. Whenever arr[fast] != 0, it writes arr[slow] = arr[fast] and increments slow++. Once fast reaches the end, all remaining slots from slow to N-1 are filled with 0s.
    Question 5: What is the main advantage of Two Pointers over a HashMap for Two Sum on a sorted array? Answer: Two Pointers requires O(1) auxiliary space, whereas a HashMap requires O(N) extra space to store elements.