Two Pointer

The two-pointer technique is an efficient way to solve problems involving sorted arrays, linked lists, or strings. It involves using two pointers to traverse the data structure, either starting at different positions and moving toward each other, or moving in the same direction to examine or compare elements.

When to use it

You can identify problems that can be solved using the two-pointer technique if they meet one or more of these conditions:

1. The problem involves sorted data, especially arrays or strings.
2. You're asked to find or compare pairs of elements, or compute a result based on interactions between two parts of the data.
3. You need an efficient solution, typically in $O(n)$ time.

Why use it

The two-pointer technique avoids the need for nested loops by moving the pointers independently, optimizing what could otherwise be a brute force approach into a linear solution. This is particularly useful for problems involving searching or comparing pairs of elements in sorted arrays or strings.

How it works

The two pointers can either move toward each other or in the same direction, depending on the problem.

Example 1: Pointers moving toward each other. Find two numbers in a sorted array that sum to a target value.

Python
nums = [1, 2, 3, 4, 6]
target = 6
left, right = 0, len(nums) - 1

while left < right:
    current_sum = nums[left] + nums[right]
    if current_sum == target:
        print(f"Pair found: ({nums[left]}, {nums[right]})")
        break
    elif current_sum < target:
        left += 1  # move left pointer to increase sum
    else:
        right -= 1  # move right pointer to decrease sum

Here, the left pointer starts at the beginning and the right pointer starts at the end. The pointers move toward each other, adjusting based on the sum.

Example 2: Pointers moving in the same direction. Given a sorted array, remove duplicates in-place and return the length of the modified array. The first pointer moves through the array, while the second pointer tracks where the next unique element should go.

Python
nums = [0, 0, 1, 1, 1, 2, 3, 3, 4]
if not nums:
    print(0)

i = 0  # pointer for the unique elements
for j in range(1, len(nums)):
    if nums[j] != nums[i]:
        i += 1
        nums[i] = nums[j]  # place the next unique element
print(i + 1)  # new length of the array

Here, both pointers start at the beginning of the array, with one pointer (j) iterating through the array, and the other pointer (i) tracking the position for unique elements. The pointers move in the same direction, with i advancing only when a new unique element is found.

Examples

1. Trapping rain water
   • Problem: Given an elevation map (height array), compute how much water it can trap after raining.
   • Approach: Use two pointers at each end of the array to calculate water trapped at each step, moving inward while maintaining the boundary of the higher elevation.
2. Find the maximum area between two lines
   • Problem: Given an array representing heights of vertical lines on a graph, find the pair of lines that can contain the most water.
   • Approach: Use two pointers starting from the ends of the array and adjust based on the height, keeping track of the maximum area.

The two-pointer technique simplifies many problems that require searching, comparing, or processing pairs of elements by reducing redundant operations, often resulting in an $O(n)$ solution.