Two Pointer Pattern

The Two Pointer Pattern is one of the most vital interview optimization techniques for arrays, strings, linked lists, and searching algorithms. Many linear data structure problems that naturally invite a brute-force approach using nested loops—costing $O(N^2)$ runtime—can be dramatically optimized to linear $O(N)$ time complexity using this pattern.

What is the Two Pointer Pattern?

Instead of managing a single traversal index variable (like i), we instantiate two active pointer tracking indexes within the collection simultaneously. Depending on the logic constraints of the problem, these tracking points are commonly referred to as left and right, or slow and fast. They update their positional values incrementally based on precise evaluation conditions.

Why Use Two Pointers?

Consider this classic challenge: Find two distinct numbers in a sorted list whose sum equals exactly 10.

Given the array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

The Naive Brute Force Approach:

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == 10) {
            // Found combination
        }
    }
}

This approach evaluates every single structural pair permutation independently, leading to a costly $O(N^2)$ runtime. By utilizing a two-pointer approach, we can scan from both ends simultaneously, reducing the runtime to $O(N)$ while executing in constant $O(1)$ space.

Types of Two Pointer Techniques

Two-pointer execution paths generally fall under two primary behavioral sub-categories:

1. Opposite Direction Pointers

The pointers begin at opposite ends of the data sequence and march toward the center.

left ------------>          <------------ right

• Commonly Used In: Pair Sum verification, Palindrome checking, Container With Most Water, and processing bounded sorted arrays.

2. Same Direction Pointers (Slow-Fast / Read-Write)

Both pointers start from the beginning of the structure but traverse forward at different speeds or under different conditional triggers.

slow ---->
fast -------->

• Commonly Used In: Duplicate removal, in-place element filtering (e.g., Move Zeros), linked list cycle detection, and array string compression schemas.

---

Problem 1: Pair Sum (Opposite Direction)

Problem Statement: Given a sorted array [1, 2, 3, 4, 6], find a pair of elements that sum up to exactly 6.

Expected Output: 2 4 (since $2 + 4 = 6$)

Two Pointer Logic

Because the array is guaranteed to be sorted, we can set left = 0 and right = n - 1. We then compute the cumulative sum of the elements at these two pointers:

• Step 1: arr[left] + arr[right] $\rightarrow$ $1 + 6 = 7$. Since $7 > 6$, our current sum is too large. Moving the left pointer rightward would only make the sum larger. To decrease the sum, we move the right pointer inward: right--.
• Step 2: $1 + 4 = 5$. Since $5 < 6$, our sum is too small. To find a larger value, we advance the left pointer: left++.
• Step 3: $2 + 4 = 6$. The target sum is found!

C Code Implementation

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 3, 4, 6};
    int n = 5;
    int target = 6;

    int left = 0;
    int right = n - 1;

    while (left < right) {
        int sum = arr[left] + arr[right];

        if (sum == target) {
            printf("%d %d\n", arr[left], arr[right]); // Output: 2 4
            break;
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
    return 0;
}

Complexity: Time: $O(N)$ | Space: $O(1)$

---

Problem 2: Remove Duplicates (Same Direction)

Problem Statement: Modify a sorted array containing duplicates, such as [1, 1, 2, 2, 3, 4, 4, 5], in place so that unique elements occupy the first positions. Return the total count of unique entries.

Expected Transformation: First 5 elements become 1 2 3 4 5.

Two Pointer Logic

We establish a slow write pointer and a fast read scanning pointer. The slow pointer marks the boundary of our unique elements array, while fast scans ahead to find new unique elements.

• Initialize slow = 0, fast = 1.
• If arr[fast] == arr[slow], skip it because it is a duplicate.
• If arr[fast] != arr[slow], increment slow, then copy the unique element: arr[slow] = arr[fast].

C Code Implementation

#include <stdio.h>

int main() {
    int arr[] = {1, 1, 2, 2, 3, 4, 4, 5};
    int n = 8;
    int slow = 0;

    for (int fast = 1; fast < n; fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }

    printf("Length = %d\n", slow + 1); // Output: 5
    for (int i = 0; i <= slow; i++) {
        printf("%d ", arr[i]); // Output: 1 2 3 4 5
    }
    printf("\n");
    return 0;
}

Complexity: Time: $O(N)$ | Space: $O(1)$

---

Problem 3: Container With Most Water (Interview Favorite)

Problem Statement: Given an array of vertical line heights [1, 8, 6, 2, 5, 4, 8, 3, 7], find two lines that form a container that holds the maximum volume of water.

Core Mathematical Insight

The water volume contained between any two lines at positions left and right is limited by the shorter line, multiplied by the distance between them:

$$\text{Area} = \min(\text{height}[\text{left}], \text{height}[\text{right}]) \times (\text{right} - \text{left})$$

A brute-force solution checks every single pair, running in $O(N^2)$ time. With a two-pointer approach, we start with the maximum possible width by placing pointers at the boundaries: left = 0 and right = n - 1. To find a larger area as the width decreases, our only option is to look for taller lines. Therefore, we always shift the pointer pointing to the shorter wall inward.

C Code Implementation

#include <stdio.h>

int main() {
    int h[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    int n = 9;

    int left = 0;
    int right = n - 1;
    int maxArea = 0;

    while (left < right) {
        int height = (h[left] < h[right]) ? h[left] : h[right];
        int width = right - left;
        int area = height * width;

        if (area > maxArea) {
            maxArea = area;
        }

        if (h[left] < h[right]) {
            left++;
        } else {
            right--;
        }
    }

    printf("Maximum Area = %d\n", maxArea); // Output: 49
    return 0;
}

Complexity: Time: $O(N)$ since each element is visited at most once | Space: $O(1)$

---

Interview Recognition Guide

Look for these common problem terms to determine which two-pointer variation to use:

Problem Phrases	Recommended Strategy	Classic Problem Examples
"Find a pair/triplet...", "Target sum in sorted array"	Opposite End Pointers	Two Sum (Sorted), 3Sum, 4Sum
"In-place modification", "Remove/filter values", "Compress"	Same Direction (Slow-Fast)	Remove Duplicates, Move Zeroes, Sort Colors
"Check string symmetry", "Bounded geometric area optimization"	Opposite End Pointers	Valid Palindrome, Container With Most Water, Trapping Rain Water

Pattern Blueprint Cheat-Sheet

Template 1: Opposite Direction Strategy

int left = 0;
int right = n - 1;
while (left < right) {
    if (met_condition) {
        // Process logic
        left++; // or right--
    } else if (sum_too_large) {
        right--;
    } else {
        left++;
    }
}

Template 2: Same Direction (Slow-Fast) Strategy

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (is_valid_element) {
        arr[slow] = arr[fast];
        slow++;
    }
}

Frequently Asked Questions (FAQs)

1. Can I use the opposite-direction pair sum approach if the input array is unsorted?

No. The opposite-direction strategy relies on the array being sorted so you can make predictable decisions about which pointer to move based on the target sum. If the array is unsorted, you must either sort it first ($O(N \log N)$ time) or use a hash table to find pairs in $O(N)$ time and space.

2. How do I choose between the Sliding Window pattern and the Two Pointer pattern?

While both methods use two indicators, the Sliding Window pattern expands or shrinks an inclusive continuous subsegment to trace properties within that window (like sum or character frequency). The Two Pointer pattern typically focuses on comparing independent element pairs (such as boundaries or read/write locations) rather than the elements between them.

3. What is the "Runner" variant of the same-direction two-pointer technique?

The runner technique moves the fast pointer at a constant multiple of the speed of the slow pointer (for example, moving 2 nodes per step instead of 1). This is a standard approach used to find the midpoint of a linked list or to detect cycles (Floyd's Tortoise and Hare algorithm).