Two Pointers Pattern

The Two Pointers Pattern is one of the most important algorithmic problem-solving techniques. Instead of repeatedly scanning a data structure with nested loops, two indices (pointers) move through the data in a coordinated manner. This often reduces time complexity from O(n²) to O(n) while maintaining constant or minimal extra space.

This pattern appears frequently in:

• Coding interviews – a high‑value tool for array, string, and linked list problems.
• Data processing pipelines – filtering, merging, and partitioning streams.
• Search problems – finding pairs, triplets, or sub‑ranges efficiently.
• Optimization problems – maximising area, container volume, or trapped water.
• In‑place transformations – removing duplicates, moving zeros, or partitioning.

Mastering the Two Pointers Pattern gives you a reusable mental model that transfers across dozens of classic problems.

---

Why the Pattern Matters

A common brute‑force approach for many problems uses nested loops. For example, finding all pairs that sum to a target in an unsorted array might look like:

for i in range(n):
    for j in range(i+1, n):
        if arr[i] + arr[j] == target:
            # found a pair

This O(n²) scan becomes prohibitively slow as the input size grows. When the array is sorted, two pointers can replace the inner loop with a single O(n) pass, improving scalability by orders of magnitude.

Key benefits:

• Scalability – linear or near‑linear runtime on large inputs.
• Performance – eliminates redundant work by never revisiting elements that cannot be part of the solution.
• Simplicity – once recognised, the code is cleaner and easier to reason about than nested loops.

---

Core Idea

Two pointers represent two positions in a data structure – often an array, string, or linked list. They move according to problem‑specific rules, shrinking the search space at each step.

Visual example for opposite‑direction pointers:

Left Pointer →        ← Right Pointer
   Index 0               Index n-1

The pointers close in, examining the elements they point to.

At each step, the algorithm decides which pointer to move based on a condition. Because both pointers only move forward (or inward), the total work is proportional to the number of elements – O(n).

---

When Should You Use Two Pointers?

Recognise the pattern by looking for these signals.

Problem Signal	Pattern Candidate
Sorted Array	The data is sorted, or sorting first is acceptable (O(n log n) pre‑processing).
Pair Search	You need to find two elements that satisfy a condition (sum, difference, etc.).
Opposite Ends	The problem can be approached from both boundaries (palindrome, container, trapping water).
Symmetry Checks	Comparison between mirrored positions (palindrome, reverse check).
Duplicate Removal	In‑place removal of duplicates from a sorted sequence.
Partitioning Problems	Rearranging elements around a pivot or condition (move zeros, three‑way partition).
Palindrome Validation	Checking equality while moving from both ends towards the centre.

If one or more of these signals are present, the Two Pointers Pattern is likely to yield an optimal solution.

---

Pattern Variations Overview

Variation	Description
Opposite Direction Pointers	One pointer starts at the beginning, the other at the end; they move towards each other.
Same Direction Pointers	Both pointers start at the beginning; one acts as a reader, the other as a writer.
Fast and Slow Pointers	One pointer moves faster than the other, often used in cycle detection or middle‑finding.
Partitioning Pointers	Pointers divide the array into regions based on a pivot or condition.
Multiple Pointer Variants	Three or more pointers used for problems like 3Sum or merging sorted arrays.

Each variation is a specialised tool within the broader pattern.

---

Variation 1: Opposite Direction Pointers

Concept
Place one pointer at the start (left = 0) and the other at the end (right = n‑1). Move them inward based on the current state. Useful for pair searches in sorted arrays, palindromes, and area optimisation.

Example: Two Sum in Sorted Array
Given a sorted array of integers and a target sum, return the indices (1‑based) of the two numbers that add up to the target.

Step‑by‑step walkthrough

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1‑based indexing
        elif current_sum < target:
            left += 1   # need a larger sum → move left forward
        else:
            right -= 1  # need a smaller sum → move right backward

Pointer movement visualization

Array: [2, 7, 11, 15], target = 9

Step 1: left=0 (2), right=3 (15) → sum=17 > 9 → right--
Step 2: left=0 (2), right=2 (11) → sum=13 > 9 → right--
Step 3: left=0 (2), right=1 (7)  → sum=9 == target → return [1,2]

Complexity Analysis
Time: O(n) – each element visited at most once.
Space: O(1) – only two pointers used.

---

Variation 2: Same Direction Pointers

Concept
Both pointers start at the beginning. One pointer (the “fast” or “read” pointer) scans the data, while the other (the “slow” or “write” pointer) keeps track of the position for the next valid element. This enables in‑place modifications with a single pass.

Example: Remove Duplicates from Sorted Array
Given a sorted array, remove duplicates in‑place and return the length of the new subarray containing unique elements.

Pointer behaviour

• write pointer tracks where the next unique element should go.
• read pointer scans through the array.

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1  # position for the next unique element
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write

Walkthrough

Input: [1, 1, 2]
read=1: nums[1]==nums[0] → skip
read=2: nums[2]!=nums[1] → copy to write=1, write becomes 2
Result: [1, 2, _], length = 2

The write pointer only moves forward when a new unique value is found, ensuring O(n) time and O(1) extra space.

---

Variation 3: Fast and Slow Pointers

Concept
One pointer moves at a different speed than the other. Typically, the slow pointer advances one step while the fast pointer advances two. This technique is heavily used in linked list problems.

Example: Detect Cycle in Linked List
Determine if a linked list contains a cycle.

Algorithm

• Initialise both slow and fast to the head.
• Slow moves one node per iteration; fast moves two.
• If there is a cycle, they will eventually meet (collision).
• If fast reaches the end (null), no cycle exists.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Why collision indicates a cycle
In a cyclic list, the fast pointer catches up to the slow pointer from behind because the relative speed difference is one node per step, guaranteeing a meeting within a bounded number of iterations.

---

Variation 4: Partitioning Pointers

Concept
Pointers are used to rearrange elements into groups based on a pivot or condition. This in‑place partitioning is the core of quicksort and many array segregation problems.

Example: Partition Array Around Pivot
Reorder elements so that all values less than the pivot appear first, followed by all elements equal or greater than the pivot.

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1  # boundary for smaller elements
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

Engineering benefits

• In‑place rearrangement avoids additional array allocations.
• Foundation for efficient sorting (QuickSort) and selection algorithms (QuickSelect).
• Useful in real‑world data processing where categorisation must happen with minimal memory overhead.

---

Complexity Analysis

Variation	Time Complexity	Space Complexity
Opposite Direction	O(n)	O(1)
Same Direction	O(n)	O(1)
Fast & Slow	O(n)	O(1)
Partitioning	O(n)	O(1)
Multiple Pointers (e.g., 3Sum)	O(n²) after sorting	O(1) (or O(n) for output)

The pattern is often optimal because it scans the data exactly once, never backtracking unnecessarily. The constant space footprint makes it suitable for memory‑constrained environments.

---

Detailed Example: Two Sum II

Problem
Given a 1‑indexed sorted array of integers numbers and an integer target, return the indices of the two numbers such that they add up to target. You may assume exactly one solution exists and you may not use the same element twice.

Input
numbers = [2, 7, 11, 15], target = 9

Expected output
[1, 2] (because 2 + 7 = 9)

Pointer movements

1. left=0, right=3, sum=17 → too large, move right to 2
2. left=0, right=2, sum=13 → too large, move right to 1
3. left=0, right=1, sum=9 → match, return [left+1, right+1]

Reasoning
Because the array is sorted, moving left forward increases the sum; moving right backward decreases it. The decision at each step is deterministic, guaranteeing no missed pairs.

Complexity
Time O(n), space O(1). Even if we had sorted the array first, the overall O(n log n) time for sorting plus O(n) two‑pointer scan is far better than O(n²) brute force.

---

Detailed Example: Valid Palindrome

Problem
Check if a given string is a palindrome, considering only alphanumeric characters and ignoring case.

Two‑pointer approach
Place one pointer at the start, another at the end. While left < right, skip non‑alphanumeric characters, then compare the characters at both pointers (case‑insensitively). If they differ, the string is not a palindrome.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Early termination
As soon as a mismatch is found, the algorithm returns False, avoiding unnecessary work. The two pointers never cross the middle, performing at most n/2 comparisons.

---

Detailed Example: Container With Most Water

Problem
Given an array of non‑negative integers height where each element represents the height of a vertical line, find two lines that together with the x‑axis form a container that holds the most water.

Brute force – O(n²)
Check every pair of lines and compute the area: min(height[i], height[j]) * (j - i). This is too slow for large inputs.

Two‑pointer intuition
Start with the widest possible container (left=0, right=n-1). The area is limited by the shorter line. To potentially increase the area, move the pointer pointing to the shorter line inward, because a taller line further inward might compensate for the reduced width.

def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, h * width)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water

Why O(n)
The search space shrinks by one at each step, resulting in a linear scan. No re‑examination of previous pairs is needed because a taller line combined with any shorter one would have already been considered with the original boundaries.

---

Common Interview Problems

Problem	Variant Used
Two Sum II (Sorted Array)	Opposite Direction
Valid Palindrome	Opposite Direction
Remove Duplicates from Sorted Array	Same Direction
Move Zeroes	Same Direction / Partitioning
Container With Most Water	Opposite Direction
Trapping Rain Water	Opposite Direction (multiple passes)
Linked List Cycle	Fast & Slow
3Sum	Opposite Direction (with outer loop)
Palindrome Linked List	Fast & Slow + Reverse

Each of these problems can be solved optimally once the appropriate two‑pointer variation is identified.

---

Pattern Recognition Framework

Ask yourself these questions when analysing a new problem:

1. Is the data sorted? Sorting may unlock a two‑pointer solution.
2. Am I searching for pairs? Any problem that asks for two elements satisfying a constraint is a prime candidate.
3. Can I process from both ends? Symmetry or extreme‑value optimisation often suggests opposite‑direction pointers.
4. Can one scan while another tracks progress? For in‑place modifications or reading/writing, same‑direction pointers apply.
5. Can I eliminate repeated work? If a brute‑force solution revisits elements that can logically be excluded, two pointers can skip them.

Answering “yes” to any of these strongly indicates the Two Pointers Pattern is applicable.

---

Common Mistakes

Moving the Wrong Pointer

In problems like Two Sum II, moving the pointer towards a larger or smaller value must be the opposite of what the current sum suggests. Incorrect direction leads to missed pairs or infinite loops.

Missing Sorted‑Data Assumptions

Many two‑pointer solutions require a sorted input. If the data is unsorted, you must sort it first (usually O(n log n)). Always verify whether sorting is allowed or if the problem guarantees order.

Off‑by‑One Errors

Pointers initialised to 0 and n‑1 must be updated correctly (e.g., left++, right--). For same‑direction pointers, careful handling of the first element prevents skipping the first value.

Infinite Loops

When both pointers can stop moving under certain conditions (e.g., both skip invalid characters in palindrome check), the outer while left < right must be coupled with inner skip loops that also respect the left < right condition.

Forgetting Edge Cases

Empty arrays, single‑element arrays, strings with only non‑alphanumeric characters, and already‑unique arrays must be handled gracefully to avoid index‑out‑of‑bounds or incorrect results.

---

Engineering Applications

Stream Processing

When processing a continuous stream of sorted events (e.g., log timestamps), two pointers can efficiently correlate events within a time window without storing the entire stream.

Log Analysis

Merging two pre‑sorted log files from different services can be done with a same‑direction two‑pointer merge, avoiding full in‑memory sorting.

Memory Optimisation

In‑place algorithms using two pointers consume O(1) additional memory, critical in embedded systems, large‑data frameworks, and environments where allocations are expensive.

Search Systems

Range queries and intersection of sorted posting lists in information retrieval often use two‑pointer techniques to compute intersections in linear time.

Data Validation

Checking for balanced quotes, brackets, or symmetry in configuration files can be modelled as a two‑pointer scan from both ends, even if the data is not numeric.

---

Two Pointers vs Sliding Window

Aspect	Two Pointers	Sliding Window
Pointer movement	Pointers move independently or toward each other; no fixed window size.	Window boundaries move together, maintaining a contiguous segment.
Focus	Pair relationships, symmetry, partitioning.	Subarray or substring properties under a dynamic constraint.
Typical input	Sorted arrays, linked lists, strings.	Unsorted arrays or strings where a contiguous range matters.
Example problems	Two Sum II, Valid Palindrome, Container With Most Water.	Maximum sum subarray of size k, longest substring without repeating characters.
When to use	Problem asks for two elements, in‑place modification, or cycle detection.	Problem asks for a subarray/substring length, sum, or condition on a window.

Similarities
Both patterns avoid nested loops by maintaining dynamic indices, achieving O(n) time. They are often introduced together as core linear‑scan techniques.

Difference
Sliding window maintains a “window” that expands or contracts based on a condition, while two pointers often target specific elements at the ends or relative positions. Same‑direction two‑pointer variants (reader/writer) closely resemble a sliding window of variable size but without a constraint on window contents.

---

Pattern Cheat Sheet

Signal	Recommended Pointer Strategy
Sorted array + pair sum/target	Opposite direction
Check palindrome / symmetry	Opposite direction
Remove duplicates from sorted array	Same direction (reader/writer)
Move all zeros to the end	Same direction (read + write) or partitioning
Optimise area/volume between two ends	Opposite direction
Detect cycle in linked list	Fast & Slow
Find middle of linked list	Fast & Slow
Partition around pivot	Partitioning pointers
Three‑sum, four‑sum	Outer loop + opposite direction

---

Key Takeaways

1. Two pointers transform O(n²) brute‑force scans into O(n) solutions for a wide class of problems.
2. The pattern relies on sorted data or a linear ordering that enables deterministic pointer movement.
3. Opposite‑direction pointers handle pair searches and symmetry checks.
4. Same‑direction pointers enable in‑place array transformations with O(1) space.
5. Fast‑and‑slow pointers are essential for cycle detection and finding midpoints in lists.
6. Partitioning pointers underpin quicksort and on‑the‑fly data categorisation.
7. Space complexity is almost always O(1), making the pattern memory‑efficient.
8. Correct pointer update logic is critical – moving the wrong pointer breaks the algorithm.
9. Edge cases (empty input, single element, all identical values) must be tested.
10. The pattern appears in diverse engineering contexts, not just coding interviews.

---

Practice Problems

Beginner

• Valid Palindrome – apply opposite‑direction pointer skip logic.
• Remove Duplicates from Sorted Array – implement same‑direction read/write pointers.

Intermediate

• Two Sum II – Input Array Is Sorted – opposite‑direction pair search.
• Move Zeroes – same‑direction in‑place rearrangement.
• Container With Most Water – greedy two‑pointer area optimisation.

Advanced

• Trapping Rain Water – two‑pointer approach with left/right max tracking.
• 3Sum – outer loop + two‑pointer inner scan for triplets.
• Linked List Cycle II – fast‑slow detection followed by finding the cycle entrance.

---

Next Steps

The natural extension of the same‑direction two‑pointer movement is the Sliding Window Pattern, where a dynamic contiguous segment is maintained to satisfy a constraint. Understanding Two Pointers first makes Sliding Window much easier to grasp, as both rely on moving indices to avoid repeated scans.

Continue to the Sliding Window Pattern to deepen your pattern‑based problem‑solving toolkit.