Two Pointers Technique

The Two Pointers pattern optimizes searches in linear data structures by using two index variables that traverse the data simultaneously. Instead of checking all combinations with nested loops in $O(N^2)$ time, we exploit structural properties (such as sorted order) to make optimal greedy decisions at each step. This allows us to discard an entire class of invalid sub-problems in $O(1)$ time, achieving an overall $O(N)$ time complexity.

The Core Concept: Two Sum II (Sorted Array)

To understand this concept deeply, let's explore Two Sum II - Sorted Array.

Problem Statement: Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Naive Brute Force — $O(N^2)$

A naive solution checks every possible pair of elements:

def twoSumNaive(numbers: list[int], target: int) -> list[int]:
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1] # 1-based indexing
    return []

This is highly inefficient because it ignores the fact that the array is already sorted.

The Two Pointers Breakthrough — $O(N)$

We can solve this in $O(N)$ time and $O(1)$ space using two pointers: one at the beginning (left = 0) and one at the end (right = len(numbers) - 1).

At each step, we calculate the sum of the elements at the two pointers:

If the sum matches the target, we have found the answer.
If the sum is less than the target, we need a larger sum. Since the array is sorted, incrementing the left pointer will increase the sum.
If the sum is greater than the target, we need a smaller sum. Decrementing the right pointer will decrease the sum.

This decision rule eliminates the need to check any other combinations containing the discarded pointer.

Step-by-Step Traversal

Let's trace the algorithm on the array: [2, 7, 11, 15] with target 9.

Step 1: Initialization

We place left at index 0 (value 2) and right at index 3 (value 15).

SETInitialize right pointer to 31 / 16

Sorted Numbers (numbers)

Active Operation:

res

scroll to zoom · drag to pan

116

Step 2: First Calculation & Move

We calculate the sum of the values at the pointers:

$\text{Sum} = 2 + 15 = 17$ .
Since $17 > 9$ (our target), the sum is too large.

SETCalculate current sum: numbers[left] + numbers[right] = 2 + 15 = 171 / 14

Sorted Numbers (numbers)

Active Operation:

res

Variables:

sum_val

target

scroll to zoom · drag to pan

114

Any other pair using 15 with values to the right of 2 will also sum to more than 9. So, we can safely discard 15 by decrementing right to 2 (value 11).

SETsum_val > target -> decrement right pointer: right = 21 / 11

Sorted Numbers (numbers)

Active Operation:

res

Variables:

sum_val

target

scroll to zoom · drag to pan

111

Step 3: Second Calculation & Move

The pointers are now at left = 0 (value 2) and right = 2 (value 11).

$\text{Sum} = 2 + 11 = 13$ .
Since $13 > 9$ , the sum is still too large.

SETCalculate current sum: numbers[left] + numbers[right] = 2 + 11 = 131 / 9

Sorted Numbers (numbers)

Active Operation:

res

Variables:

sum_val

target

scroll to zoom · drag to pan

We decrement the right pointer again, moving right to 1 (value 7).

SETsum_val > target -> decrement right pointer: right = 11 / 6

Sorted Numbers (numbers)

Active Operation:

res

Variables:

sum_val

target

scroll to zoom · drag to pan

Step 4: Solution Found

The pointers are now at left = 0 (value 2) and right = 1 (value 7).

$\text{Sum} = 2 + 7 = 9$ .
The sum matches the target!

FOUNDFound pair that sums to target: indices 1 and 21 / 2

Sorted Numbers (numbers)

Active Operation:

res

Variables:

sum_val

target

scroll to zoom · drag to pan

We return the 1-based indices: [1, 2].

DONEDone! Solution found: 1-indexed indices [1, 2]1 / 1

Sorted Numbers (numbers)

Active Operation:

res

scroll to zoom · drag to pan

Code Implementation

def twoSum(numbers: list[int], target: int) -> list[int]:
    left = 0
    right = 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   # sum too small -> move left forward to increase it
        else:
            right -= 1  # sum too big -> move right inward to decrease it
            
    return []

Time Complexity: $O(N)$ — we scan the array from both ends, visiting each element at most once. Space Complexity: $O(1)$ — we only store a few pointer variables.

Core Variations

1. Opposite Ends (Two-Way Scan)

Pointers start at opposite ends and converge toward the middle. Usually requires a sorted array or geometric structure.

Use when: searching for a pair/triplet that satisfies a target sum or distance condition.
Examples: Two Sum II, Container With Most Water, 3Sum, Valid Palindrome.

2. Fast & Slow (Pointer Chase)

Two pointers advance in the same direction at different speeds (usually slow moves 1 step, fast moves 2).

Use when: detecting cycles in lists, finding middle nodes, or locating the $k$ -th element from the end.
Examples: Linked List Cycle, Middle of Linked List.

3. Read-Write (In-Place Modification)

One pointer reads each element sequentially; the other writes only valid elements back in place.

Use when: modifying or compacting an array in-place to save memory.
Examples: Move Zeroes, Remove Duplicates from Sorted Array, Sort Colors.

When Do I Use This?

Ask yourself:

Is the input array sorted, or can sorting it help without affecting the output requirements?
Am I looking for a pair or a triplet that satisfies a specific condition?
Can I make a local greedy choice to advance a pointer to eliminate other candidates?

If the answer is yes, Two Pointers is highly likely to yield an optimal $O(N)$ solution.

Practice Problems

Done	Question	Difficulty
	Container With Most Water	Medium
	3Sum	Medium
	Valid Triangle Number	Medium
	Move Zeroes	Easy
	Sort Colors	Medium
	Trapping Rain Water	Hard

Two Pointers Technique

The Core Concept: Two Sum II (Sorted Array)

Naive Brute Force — O(N2)O(N^2)O(N2)

The Two Pointers Breakthrough — O(N)O(N)O(N)

Step-by-Step Traversal

Step 1: Initialization

Step 2: First Calculation & Move

Step 3: Second Calculation & Move

Step 4: Solution Found

Code Implementation

Core Variations

1. Opposite Ends (Two-Way Scan)

2. Fast & Slow (Pointer Chase)

3. Read-Write (In-Place Modification)

When Do I Use This?

Practice Problems

Comments

Naive Brute Force — $O(N^2)$

The Two Pointers Breakthrough — $O(N)$