Two Pointers

Two pointers algorithms efficiently solve problems involving sorted arrays, pairs, or sub-arrays/sub-strings by avoiding the $O(n^2)$ complexity of nested loops. The pointers can start from the same or opposite ends of the array, and this technique is useful for maintaining linear traversal. Sliding Window (Fixed) and Sliding Window (Dynamic) are variants of two pointers.

Time Complexity: $O(n)$

Space Complexity: $O(1)$

Template

Python

def two_pointers(arr):
    left, right = 0, len(arr) - 1
    result = 0
    while left < right:
        # Process elements at left and right pointers
        # Move pointers based on condition
        if condition:
            left += 1
        else:
            right -= 1
    return result

Golang

func twoPointers(arr []int) int {
    left, right := 0, len(arr)-1
    result := 0
    for left < right {  // Golang's "WHILE" is written as "FOR"
        // Process elements at left and right pointers
        // Move pointers based on condition
        if condition {
            left++
        } else {
            right--
        }
    }
    return result
}

Examples

Two Sum II (L167)

Given a 1-indexed non-decreasing array of integers, find two numbers such that they add up to a specific target number. Return the indices of the two numbers as an array of length 2.

• left is the index of the first number
• right is the index of the second number
• condition is how arr[left] + arr[right] compares to target

Python

def two_sum(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        two_sum = arr[left] + arr[right]
        if two_sum < target:
            left += 1
        elif two_sum > target:
            right -= 1
        else:
            return [left + 1, right + 1]

Remove Duplicates from Sorted Array (L26)

Given a sorted in non-decreasing array, remove duplicates in-place by reordering such that the first k elements contain unique elements in the order they were present in the original array. Return k.

• right is the index being scanned ahead of left
• left is the index of the last unique element
• result is the number of unique elements in the array is left + 1
• condition is arr[left] == arr[right]

Python

def remove_duplicates(arr):
    left, right = 0, 1
    while right < len(arr):
        if arr[left] == arr[right]:
            right += 1
        else:
            left += 1
            arr[left] = arr[right]
            right += 1

    return left + 1

Visualization

1 1 2 2 3 3 4 4 5 5  (L = 0, R = 1)
L R

1 1 2 2 3 3 4 4 5 5  (R++)
L   R

1 2 2 2 3 3 4 4 5 5  (L++, arr[L] <- arr[R])
  L R
  ^

1 2 2 2 3 3 4 4 5 5  (R++)
  L   R

1 2 2 2 3 3 4 4 5 5  (R++)
  L     R

1 2 3 2 3 3 4 4 5 5  (L++, arr[L] <- arr[R])
    L   R
    ^

...


1 2 3 4 5 3 4 4 5 5  (K = L + 1 = 5)
        L         R

When to Use Two Pointers

1. Sorted Arrays:

   • If the input array is sorted (or can be sorted), two pointers can efficiently find pairs or ranges of elements that meet certain conditions (e.g., finding two numbers that sum to a target).
   • Example: In the "Two Sum II" problem, you can use two pointers starting from both ends of the sorted array.

2. Finding Pairs:

   • When the problem involves finding pairs of elements that satisfy a specific condition (e.g., sum, product), two pointers can help avoid the (O(n^2)) complexity of nested loops.
   • Example: In the "Container With Most Water" problem, two pointers can be used to maximize the area between two lines.

3. Subarray Problems:

   • For problems that require finding a subarray that meets certain criteria (e.g., maximum sum, longest unique substring), two pointers can help maintain a sliding window.
   • Example: In the "Longest Substring Without Repeating Characters" problem, you can use two pointers to track the start and end of the current substring.

4. Merging or Partitioning:

   • When merging two sorted arrays or partitioning an array based on a condition, two pointers can help traverse both arrays efficiently.
   • Example: Merging two sorted lists into one sorted list.

5. Space Efficiency:

   • If the problem requires in-place modifications or has constraints on space usage, two pointers can help achieve the desired result without additional data structures.

When Not to Use Two Pointers

1. Unsorted Arrays:

   • If the array is unsorted and you need to find pairs or elements based on conditions that require knowledge of the entire array, two pointers may not be effective.

2. Complex Conditions:

   • If the condition for moving the pointers is complex and cannot be easily defined, a brute-force approach might be more straightforward.

3. Non-linear Structures:

   • For problems involving trees or graphs, other traversal methods (like depth-first or breadth-first search) may be more appropriate.