Some Random Notes

Two-Pointer Pattern

7 min read

The Two Pointer Technique is an efficient programming pattern that uses two variables (pointers or indices) to traverse a linear data structure—like an array, string, or linked list—usually reducing time complexity from O(n²) to O(n)

Prerequisites

Standard two-pointer techniques (such as opposite-ends convergence) require strict management to prevent infinite loops and index out-of-bounds errors.

  • Sorted
    • Most standard two-pointer problems (e.g., opposite-ends convergence) require the underlying data structure to be sorted.
  • Pointer Placement
    • Initialize pointers at boundaries (left = 0, right = arr.length - 1).
  • Critical Guardrails
    • Bounds Check
      • Always enforce left < right (or valid index boundaries) in your loop condition to prevent ArrayIndexOutOfBoundsException.
    • Infinite Loop Prevention
      • Ensure every branch inside your loop explicitly modifies at least one pointer (left++, right--, or both) so the pointers continuously move toward convergence.

Code Example: Two-Pointer Array Reversal

public void reverseArray(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    // Guard condition prevents out-of-bounds and handles termination
    while (left < right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        // Explicit movement prevents infinite loops
        left++;
        right--;
    }
}

When to Use It

graph TD
    A[Does problem involve a linear structure Array/String/Linked List?] -->|YES| B(Is the data SORTED or order-dependent?)
    A -->|NO| X[Try other patterns Trees/Graphs]
    
    B -->|YES| C(Do you need to find a PAIR, TRIPLET, or BOUNDARIES?)
    B -->|NO| D(Do you need to check for CYCLES, find a MIDDLE, or COMPRESS IN-PLACE?)
    
    C -->|YES| E[CONVERGING POINTERS Left & Right]
    C -->|NO| F[SLIDING WINDOW Subarrays]
    
    D -->|YES| G[FAST & SLOW / SAME DIRECTION]
    D -->|NO| Y[Try Hash Maps, Sorting, or Brute Force]

    style E fill:#003366,stroke:#333,stroke-width:2px,color:#fff
    style F fill:#003366,stroke:#333,stroke-width:2px,color:#fff
    style G fill:#003366,stroke:#333,stroke-width:2px,color:#fff

The data is sorted (or can be easily sorted)

The Intuition: Sorting creates a predictable environment. If you want to change the value of your current combination, you know exactly which direction to move.

  • Example: If your current sum is too low, you move the left pointer forward to get a larger number. If the sum is too high, you move the right pointer backward to get a smaller number.

You are optimizing a brute-force O(n²) nested loop

The Intuition: If your first thought is to use an outer loop i and an inner loop j to scan through pairs or subarrays, you can almost always collapse them into a single loop using two pointers.

  • Example: Instead of checking every pair for target_sum, use one pointer at the start and one at the end, reading them simultaneously to cut down the search space dynamically.

You need to modify an array in-place (without extra space)

The Intuition: You need to rewrite parts of the array while preserving or reading other parts. One pointer keeps track of where the next valid element should be written, while the other pointer scans ahead looking for it. This allows you to manage operations within the same memory block, keeping space complexity to O(1).

  • Example: When removing duplicates or shifting zeros, the write pointer waits until the read pointer finds a non-duplicate/non-zero element.

The problem involves linear travel with linked structures

The Intuition: You cannot access elements by an index, so you must use relative distance or relative speeds to figure out structure positions.

  • Example: Moving one pointer twice as fast as the other will naturally land the slower pointer exactly at the midpoint when the fast one hits the end.

The 5 Structural Strategy Variants

Opposite Ends (Converging Pointers)

Pointers start at the left (0) and right (n-1) boundaries and move toward the center.

The two-pointer pattern you just used (moving inward from both ends with i and j) is extremely powerful and unlocks a whole family of classic string and array problems. Here are some great LeetCode questions that follow this exact same mindset:

1. Direct Variations (In-Place String/Array Modification)

  • Valid Palindrome II (LeetCode 680):
    • The Twist: You are allowed to delete at most one character to make a string a palindrome.
    • Why it fits: You use your standard two-pointer check, but when carr[i] != carr[j], you branch out and check both sub-segments (skipping either i or j) to see if either forms a valid palindrome.
  • Reverse Words in a String III (LeetCode 557):
    • The Twist: Reverse the characters of each word in a sentence while maintaining whitespace and initial word order.
    • Why it fits: You scan for spaces to find word boundaries and then apply a local two-pointer swap on the character array for each individual word.

2. The Classic Two-Pointer Core (Passing the Same Template)

  • Two Sum II - Input Array Is Sorted (LeetCode 167):
    • The Twist: Find two numbers in a sorted array that add up to a specific target.
    • Why it fits: Instead of comparing characters for equality, you compare the sum of elements at i and j against your target, moving i++ if the sum is too small or j-- if it’s too large.
  • Container With Most Water (LeetCode 11):
    • The Twist: Find two lines that together with the x-axis form a container, holding the most water.
    • Why it fits: You place pointers at the absolute left and right ends, calculate the area, and move the pointer pointing to the shorter line inward to try and find a taller boundary.
  • 3Sum (LeetCode 15):
    • The Twist: Find all unique triplets in an array that sum to zero.
    • Why it fits: You fix one number with an outer loop and then unleash the standard inward-moving two-pointer approach on the remaining subarray. Whenever you see a problem asking you to search or manipulate elements from both ends moving toward the center, or dealing with a sorted/constrained array, this two-pointer layout is almost always your best friend.

Same Direction (Fast & Slow / Reader & Writer)

Both pointers start from the beginning, but one moves faster or under different conditions than the other.

Fast & Slow (Linked Lists / Cycles)

Also known as Floyd’s Tortoise and Hare algorithm. Pointers move at different speeds (slow = slow.next, fast = fast.next.next).

Two Independent Arrays / Lists

One pointer is assigned to track the progress of each separate data structure.

Sliding Window Pattern (Extension of Two Pointers)

The two pointers act as the dynamic start and end boundaries of a subsegment/window.

Quick Comparison Matrix

StrategyWhen to use itVisualizing the movement
ConvergingFinding pairs/triplets in sorted arrays, or checking symmetric structures.[➔ ➔]
(Move toward each other)
Fast & SlowLinked Lists (cycles, midpoints) or detecting repeating patterns.[➔ ➔ ]
(One moves at 1x speed, one at 2x)
Same DirectionIn-place updates, space-saving compression, or building windows.[➔ ➔ ]
(Both move right, but at different paces)

Backlinks