Data Structures & AlgorithmsTwo-Pointer Technique

The Two-Pointer Technique

LevelIntermediate

Duration60 mins

TopicTwo-Pointer Technique

3 / 5

Opposite-Direction Pointers (Converging)

When Two Pointers Meet in the Middle

There's something elegant about starting at opposite ends of a problem and working inward. This is the essence of the converging two-pointer technique: two pointers that start at different positions and move toward each other until they meet.

This pattern appears everywhere:

Finding pairs that sum to a target in sorted arrays
Checking if a string is a palindrome
Finding containers that hold the most water
Reversing arrays in-place
Binary search (conceptually a form of converging pointers)

The power of this technique lies in its ability to eliminate large portions of the search space with each comparison. When you're searching for pairs in an array, brute force checks O(n²) pairs. Converging pointers find the answer in O(n) comparisons because each movement logically excludes many pairs at once.

What You Will Learn

This page covers the converging two-pointer pattern in depth: the mechanics of pointer movement, the mathematical reasoning behind why it works, and detailed implementations of classic problems including pair sums, palindrome checking, and container problems.

The Core Pattern

The converging two-pointer pattern follows a consistent structure:

Initialize one pointer at the start (left = 0) and one at the end (right = n-1)
Loop while left < right (pointers haven't crossed)
Evaluate the current pair (arr[left], arr[right])
Decide which pointer to move based on the evaluation
Terminate when pointers meet or a solution is found

The key insight is that pointer movement is informed by the current comparison. You don't blindly move both pointers; you move the one that brings you closer to the goal.

converging_template.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def converging_two_pointer_template(arr, target):
    """
    Generic template for converging two-pointer problems.
    
    The specific logic in the loop varies by problem,
    but the structure remains consistent.
    """
    left = 0
    right = len(arr) - 1
    result = None  # Or whatever initialization makes sense
    
    while left < right:
        # Evaluate current pair
        current = evaluate(arr[left], arr[right])
        
        if found_solution(current, target):
            result = record_solution(left, right)
            # May return here, or continue to find all solutions
        
        # Decide which pointer to move
        if should_move_left(current, target):
            left += 1
        else:
            right -= 1
    
    return result

Why left < right and not left <= right?

For pair problems, we need two distinct elements, so left must be strictly less than right. If we allowed left == right, we'd be pairing an element with itself.

For some problems (like binary search), left <= right is correct because we're considering single elements, not pairs.

Invariant maintenance:

Throughout the algorithm, we maintain this invariant:

All pairs (i, j) where i < left or j > right have been logically considered and rejected.

Each pointer movement extends the "rejected" region on one side, guaranteeing we don't miss any valid pair.

Classic Problem: Two Sum on Sorted Array

Problem Statement: Given a sorted array and a target sum, find two distinct elements that add up to the target. Return their indices.

Example:

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  (because nums[0] + nums[1] = 2 + 7 = 9)

This is the archetypal converging two-pointer problem.

Algorithm:

Start with left = 0 and right = n - 1
Calculate sum = arr[left] + arr[right]
If sum equals target: return the indices
If sum is too small: move left right (need a larger value)
If sum is too large: move right left (need a smaller value)
Repeat until pointers meet

Why this works:

The array is sorted. At any point:

arr[left] is the smallest remaining candidate
arr[right] is the largest remaining candidate

If their sum is too small, pairing arr[left] with any smaller element (none available on the left) would be even smaller—so we need a larger value for the left element. Moving left right gives us that.

Similarly, if the sum is too large, arr[right] is too big for any larger partnering element—so we move right left.

two_sum_sorted.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    """
    Find two numbers in sorted array that sum to target.
    
    Time: O(n) - each pointer moves at most n times total
    Space: O(1) - only two pointers
    
    Args:
        numbers: Sorted array of integers
        target: Target sum
    
    Returns:
        List of two indices (1-indexed as per LeetCode convention)
    """
    left = 0
    right = len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            # Found! Return 1-indexed (LeetCode convention)
            return [left + 1, right + 1]
        elif current_sum < target:
            # Sum too small, need larger values
            left += 1
        else:
            # Sum too large, need smaller values
            right -= 1
    
    # No solution found (shouldn't happen if guaranteed a solution)
    return []
 
 
def two_sum_all_pairs(numbers: list[int], target: int) -> list[tuple[int, int]]:
    """
    Find ALL pairs that sum to target (handles duplicates).
    
    Returns:
        List of (value1, value2) tuples for all valid pairs
    """
    result = []
    left = 0
    right = len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            result.append((numbers[left], numbers[right]))
            
            # Skip duplicates on both sides
            left_val = numbers[left]
            right_val = numbers[right]
            
            while left < right and numbers[left] == left_val:
                left += 1
            while left < right and numbers[right] == right_val:
                right -= 1
                
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return result
 
 
# Test
print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]  (1-indexed)
print(two_sum_sorted([2, 3, 4], 6))        # [1, 3]  (2 + 4 = 6)
 
# All pairs
print(two_sum_all_pairs([1, 1, 2, 2, 3, 3], 4))  # [(1, 3), (2, 2)]

Step-by-Step: [2, 3, 5, 8, 11, 15], target = 13
Step	Left	Right	Values	Sum	Action
1	0	5	(2, 15)	17	Too large → right--
2	0	4	(2, 11)	13	Found!

Handling Duplicates

When finding all pairs (not just one), you must skip duplicates to avoid reporting the same pair multiple times. After finding a match, advance both pointers past all copies of the current values before continuing.

Extension: Three Sum Problem

Problem Statement: Given an array, find all unique triplets that sum to zero.

Example:

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

This is a natural extension of two-sum: fix one element, then use two-pointer to find pairs that sum to the negation of the fixed element.

Approach:

Sort the array
For each element nums[i], find pairs in nums[i+1:] that sum to -nums[i]
Use converging two-pointer for the pair finding
Skip duplicates to avoid duplicate triplets

three_sum.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def three_sum(nums: list[int]) -> list[list[int]]:
    """
    Find all unique triplets that sum to zero.
    
    Time: O(n²) - for each of n elements, O(n) two-pointer
    Space: O(1) extra space (output not counted)
    
    Key insight: Reduce 3-sum to multiple 2-sum problems.
    Fix one element, two-pointer the rest.
    """
    nums.sort()  # Sort for two-pointer to work
    result = []
    n = len(nums)
    
    for i in range(n - 2):  # Leave room for two more elements
        # Optimization: if smallest element > 0, no solution possible
        if nums[i] > 0:
            break
        
        # Skip duplicates for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Two-pointer for the remaining array
        target = -nums[i]  # Find pairs that sum to -nums[i]
        left = i + 1
        right = n - 1
        
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
                
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return result
 
 
def three_sum_closest(nums: list[int], target: int) -> int:
    """
    Variant: Find the triplet sum closest to target.
    
    Same approach, but track the closest sum instead of exact match.
    """
    nums.sort()
    n = len(nums)
    closest = float('inf')
    
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            # Update closest if this sum is nearer
            if abs(current_sum - target) < abs(closest - target):
                closest = current_sum
            
            if current_sum == target:
                return target  # Can't get closer than exact match
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return closest
 
 
# Test
print(three_sum([-1, 0, 1, 2, -1, -4]))
# Output: [[-1, -1, 2], [-1, 0, 1]]
 
print(three_sum_closest([-1, 2, 1, -4], 1))
# Output: 2 (the triplet [-1, 2, 1] sums to 2)

Four Sum and Beyond

The same pattern extends to 4-sum, 5-sum, etc. Each additional sum level adds a nested loop. 4-sum: O(n³) = O(n) × O(n) × O(n) two-pointer. Generally, k-sum can be solved in O(n^(k-1)) using recursion with two-pointer at the base case.

Classic Problem: Container With Most Water

Problem Statement: Given an array of heights representing vertical lines, find two lines that, together with the x-axis, form a container that holds the most water.

Example:

Input:  heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
        (Using lines at indices 1 and 8, heights 8 and 7, width 7)
        Area = min(8, 7) × 7 = 49

Key Insight:

Water is limited by the shorter of the two lines. Area = min(height[left], height[right]) × (right - left).

Brute force checks all pairs: O(n²). But with two pointers, we achieve O(n).

Why Two-Pointer Works Here:

Start with widest possible container (left = 0, right = n-1). The width is maximized.

At each step, we move the pointer at the shorter line. Why?

Area = min(heights[left], heights[right]) × width
If heights[left] < heights[right], moving right left cannot increase area:
- Width decreases
- The limiting factor (heights[left]) stays the same or its partner gets smaller
Therefore, we eliminate this left position and try a taller one

This greedy choice is correct because moving the shorter pointer is the only way to potentially increase area.

container_water.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def max_area(height: list[int]) -> int:
    """
    Find the maximum water container formed by two lines.
    
    Time: O(n) - single pass with two pointers
    Space: O(1) - only two pointers
    
    Args:
        height: Array of line heights
    
    Returns:
        Maximum water that can be contained
    """
    left = 0
    right = len(height) - 1
    max_water = 0
    
    while left < right:
        # Calculate current container's area
        width = right - left
        h = min(height[left], height[right])
        current_area = width * h
        max_water = max(max_water, current_area)
        
        # Move the pointer at the shorter line
        # Only moving the shorter one can potentially increase area
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water
 
 
def max_area_verbose(height: list[int]) -> int:
    """Same algorithm with detailed tracing."""
    left = 0
    right = len(height) - 1
    max_water = 0
    
    print(f"Heights: {height}")
    print("=" * 50)
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        current_area = width * h
        
        print(f"left={left} (h={height[left]}), right={right} (h={height[right]})")
        print(f"  Width={width}, Height=min({height[left]},{height[right]})={h}")
        print(f"  Area={current_area}, Max so far={max(max_water, current_area)}")
        
        max_water = max(max_water, current_area)
        
        if height[left] < height[right]:
            print(f"  Moving left (shorter) from {left} to {left+1}")
            left += 1
        else:
            print(f"  Moving right from {right} to {right-1}")
            right -= 1
        print()
    
    return max_water
 
 
# Test
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(f"Maximum area: {max_area(heights)}")  # 49
 
# Detailed trace with smaller example
max_area_verbose([1, 8, 6, 2, 5])

Don't Confuse with Trapping Rain Water

Container With Most Water asks for the largest single container formed by two lines. Trapping Rain Water asks for total water trapped by all lines, considering the terrain between them. They look similar but have different solutions!

Classic Problem: Valid Palindrome

Problem Statement: Given a string, determine if it's a palindrome, considering only alphanumeric characters and ignoring case.

Example:

Input:  "A man, a plan, a canal: Panama"
Output: true  ("amanaplanacanalpanama" is a palindrome)

Palindrome checking is a natural fit for converging pointers: compare characters from both ends, moving inward.

valid_palindrome.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def is_palindrome(s: str) -> bool:
    """
    Check if string is a palindrome (alphanumeric only, case-insensitive).
    
    Time: O(n) - single pass
    Space: O(1) - no extra string created
    """
    left = 0
    right = len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        
        # Skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True
 
 
def is_palindrome_number(x: int) -> bool:
    """
    Check if an integer is a palindrome (without converting to string).
    
    Trick: Reverse half the number and compare.
    E.g., 12321 -> compare 123 and 12 (after reversing half)
    """
    # Negative numbers and numbers ending in 0 (except 0) aren't palindromes
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    
    reversed_half = 0
    
    # Build reversed second half
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10
    
    # For odd-length: middle digit is in reversed_half, divide by 10 to ignore
    return x == reversed_half or x == reversed_half // 10
 
 
def valid_palindrome_ii(s: str) -> bool:
    """
    Can we make the string a palindrome by removing at most ONE character?
    
    LeetCode 680: Valid Palindrome II
    
    Strategy: Use two pointers, when mismatch found, try skipping either char.
    """
    def is_palindrome_range(s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    
    left = 0
    right = len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            # Try skipping left char or right char
            return (is_palindrome_range(s, left + 1, right) or 
                    is_palindrome_range(s, left, right - 1))
        left += 1
        right -= 1
    
    return True
 
 
# Tests
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))                       # False
 
print(is_palindrome_number(121))    # True
print(is_palindrome_number(-121))   # False
print(is_palindrome_number(10))     # False
 
print(valid_palindrome_ii("abca"))  # True (remove 'c' or 'b')
print(valid_palindrome_ii("abc"))   # False

Palindrome Variations

Palindrome problems have many variations: can you make it a palindrome by removing k characters? What's the minimum insertions to make it a palindrome? What's the longest palindromic substring? The two-pointer approach works directly for the basic check; variations may require dynamic programming or other techniques.

Reversing Arrays and Strings In-Place

One of the simplest applications of converging pointers is in-place reversal. Swap elements from both ends, moving inward until the pointers meet.

This pattern is a building block for more complex algorithms:

Rotating arrays (reverse parts, then reverse whole)
Reversing words in a sentence
Reversing linked lists (conceptually similar)

reverse_in_place.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
def reverse_array(arr: list) -> None:
    """
    Reverse array in-place using two pointers.
    
    Time: O(n) - n/2 swaps
    Space: O(1) - in-place
    """
    left = 0
    right = len(arr) - 1
    
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
 
 
def reverse_string(s: list[str]) -> None:
    """
    Reverse string (given as list of characters) in-place.
    
    Note: In Python, strings are immutable, so we work with char list.
    """
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
 
 
def reverse_words(s: list[str]) -> None:
    """
    Reverse words in a string in-place.
    
    Example: "hello world" -> "world hello"
    
    Strategy:
    1. Reverse entire string: "dlrow olleh"
    2. Reverse each word: "world hello"
    """
    def reverse_range(arr, left, right):
        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    
    n = len(s)
    
    # Step 1: Reverse entire string
    reverse_range(s, 0, n - 1)
    
    # Step 2: Reverse each word
    start = 0
    for i in range(n + 1):
        if i == n or s[i] == ' ':
            reverse_range(s, start, i - 1)
            start = i + 1
 
 
def rotate_array(nums: list[int], k: int) -> None:
    """
    Rotate array to the right by k steps in-place.
    
    Example: [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]
    
    Strategy: Three reverses
    1. Reverse all: [7,6,5,4,3,2,1]
    2. Reverse first k: [5,6,7,4,3,2,1]
    3. Reverse rest: [5,6,7,1,2,3,4]
    """
    def reverse_range(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
    
    n = len(nums)
    k = k % n  # Handle k > n
    
    reverse_range(0, n - 1)      # Reverse all
    reverse_range(0, k - 1)       # Reverse first k
    reverse_range(k, n - 1)       # Reverse remaining
 
 
# Tests
arr = [1, 2, 3, 4, 5]
reverse_array(arr)
print(arr)  # [5, 4, 3, 2, 1]
 
chars = list("hello world")
reverse_words(chars)
print(''.join(chars))  # "world hello"
 
nums = [1, 2, 3, 4, 5, 6, 7]
rotate_array(nums, 3)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

The Triple Reverse Trick

The 'reverse all, then reverse parts' technique is incredibly powerful. It works for array rotation and reversing words because reversing twice in overlapping regions effectively shifts elements to their correct positions. Understanding why this works deepens your grasp of array manipulation.

Problem: Squares of a Sorted Array

Problem Statement: Given an array sorted in non-decreasing order, return an array of the squares of each number, also in non-decreasing order.

Example:

Input:  [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]

Challenge: With negative numbers, simply squaring and keeping order doesn't work:

(-4)² = 16, (-1)² = 1, 0² = 0, 3² = 9, 10² = 100
Naive squares: [16, 1, 0, 9, 100] - not sorted!

Two-Pointer Insight:

After squaring, the largest values come from either end (most negative or most positive). Use converging pointers to build the result from the largest to smallest.

sorted_squares.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def sorted_squares(nums: list[int]) -> list[int]:
    """
    Return squares of sorted array in non-decreasing order.
    
    Time: O(n) - single pass with two pointers
    Space: O(n) - for result array
    
    Key insight: Largest squares are at the ends (most negative or positive).
    Build result from end to start.
    """
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1
    pos = n - 1  # Fill from end
    
    while left <= right:
        left_sq = nums[left] ** 2
        right_sq = nums[right] ** 2
        
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
        
        pos -= 1
    
    return result
 
 
def sorted_squares_verbose(nums: list[int]) -> list[int]:
    """Same algorithm with step-by-step trace."""
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1
    pos = n - 1
    
    print(f"Input: {nums}")
    print(f"Result size: {n}, filling from position {pos}")
    print()
    
    while left <= right:
        left_sq = nums[left] ** 2
        right_sq = nums[right] ** 2
        
        print(f"left={left} ({nums[left]}²={left_sq}), right={right} ({nums[right]}²={right_sq})")
        
        if left_sq > right_sq:
            print(f"  Left square larger, result[{pos}] = {left_sq}")
            result[pos] = left_sq
            left += 1
        else:
            print(f"  Right square larger/equal, result[{pos}] = {right_sq}")
            result[pos] = right_sq
            right -= 1
        
        pos -= 1
        print(f"  Result so far: {result}")
        print()
    
    return result
 
 
# Test
nums = [-4, -1, 0, 3, 10]
print(sorted_squares_verbose(nums))

Why we use left <= right here:

Unlike pair-finding where we need two distinct elements, here we're processing every element once. The condition left <= right ensures we process the final element when both pointers meet.

Summary: Opposite-Direction Pointers

You've now mastered the converging two-pointer pattern. Let's consolidate the key insights:

Key Takeaways

•Start at opposite ends — One pointer at start, one at end. Move based on comparison outcomes.
•Each move eliminates many candidates — This is why O(n²) pair searches become O(n).
•Sorted data unlocks this pattern — The ordering is what makes intelligent movement possible.
•Two-sum generalizes to k-sum — Nest loops for k-sum; innermost uses two-pointer.
•Container/optimization problems — Move the pointer that limits the objective (shortest line, etc.).
•Palindrome checking — Natural fit: compare from both ends.
•In-place reversal — Swap from ends, move inward. Foundation for rotations and word reversal.

Converging Two-Pointer Problem Types
Problem Type	Left Movement	Right Movement	Termination
Two sum (sorted)	sum < target	sum > target	Pointers meet or solution found
Container water	height[left] < height[right]	height[left] >= height[right]	Pointers meet
Palindrome check	After comparing	After comparing	Pointers meet or mismatch
In-place reverse	Always	Always	Pointers meet
Sorted squares	left² > right²	left² <= right²	Pointers cross

What's next:

In the next page, we'll explore classic two-pointer problems in greater depth—the canonical problems you'll encounter repeatedly in interviews and real-world scenarios, including removing duplicates, partitioning, and the pair sum family.

Page Complete

You now have deep command of opposite-direction two-pointer techniques. These patterns form the foundation for pair-finding, optimization, and symmetry-checking algorithms.

3 / 5

Loading learning content...

Data Structures & AlgorithmsTwo-Pointer Technique

The Two-Pointer Technique

LevelIntermediate

Duration60 mins

TopicTwo-Pointer Technique

3 / 5

Opposite-Direction Pointers (Converging)

When Two Pointers Meet in the Middle

This pattern appears everywhere:

Finding pairs that sum to a target in sorted arrays
Checking if a string is a palindrome
Finding containers that hold the most water
Reversing arrays in-place
Binary search (conceptually a form of converging pointers)

What You Will Learn

The Core Pattern

The converging two-pointer pattern follows a consistent structure:

Initialize one pointer at the start (left = 0) and one at the end (right = n-1)
Loop while left < right (pointers haven't crossed)
Evaluate the current pair (arr[left], arr[right])
Decide which pointer to move based on the evaluation
Terminate when pointers meet or a solution is found

The key insight is that pointer movement is informed by the current comparison. You don't blindly move both pointers; you move the one that brings you closer to the goal.

converging_template.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def converging_two_pointer_template(arr, target):
    """
    Generic template for converging two-pointer problems.
    
    The specific logic in the loop varies by problem,
    but the structure remains consistent.
    """
    left = 0
    right = len(arr) - 1
    result = None  # Or whatever initialization makes sense
    
    while left < right:
        # Evaluate current pair
        current = evaluate(arr[left], arr[right])
        
        if found_solution(current, target):
            result = record_solution(left, right)
            # May return here, or continue to find all solutions
        
        # Decide which pointer to move
        if should_move_left(current, target):
            left += 1
        else:
            right -= 1
    
    return result

Why left < right and not left <= right?

For pair problems, we need two distinct elements, so left must be strictly less than right. If we allowed left == right, we'd be pairing an element with itself.

For some problems (like binary search), left <= right is correct because we're considering single elements, not pairs.

Invariant maintenance:

Throughout the algorithm, we maintain this invariant:

All pairs (i, j) where i < left or j > right have been logically considered and rejected.

Each pointer movement extends the "rejected" region on one side, guaranteeing we don't miss any valid pair.

Classic Problem: Two Sum on Sorted Array

Problem Statement: Given a sorted array and a target sum, find two distinct elements that add up to the target. Return their indices.

Example:

Input:  nums = [2, 7, 11, 15], target = 9
Output: [0, 1]  (because nums[0] + nums[1] = 2 + 7 = 9)

This is the archetypal converging two-pointer problem.

Algorithm:

Start with left = 0 and right = n - 1
Calculate sum = arr[left] + arr[right]
If sum equals target: return the indices
If sum is too small: move left right (need a larger value)
If sum is too large: move right left (need a smaller value)
Repeat until pointers meet

Why this works:

The array is sorted. At any point:

arr[left] is the smallest remaining candidate
arr[right] is the largest remaining candidate

Similarly, if the sum is too large, arr[right] is too big for any larger partnering element—so we move right left.

two_sum_sorted.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    """
    Find two numbers in sorted array that sum to target.
    
    Time: O(n) - each pointer moves at most n times total
    Space: O(1) - only two pointers
    
    Args:
        numbers: Sorted array of integers
        target: Target sum
    
    Returns:
        List of two indices (1-indexed as per LeetCode convention)
    """
    left = 0
    right = len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            # Found! Return 1-indexed (LeetCode convention)
            return [left + 1, right + 1]
        elif current_sum < target:
            # Sum too small, need larger values
            left += 1
        else:
            # Sum too large, need smaller values
            right -= 1
    
    # No solution found (shouldn't happen if guaranteed a solution)
    return []
 
 
def two_sum_all_pairs(numbers: list[int], target: int) -> list[tuple[int, int]]:
    """
    Find ALL pairs that sum to target (handles duplicates).
    
    Returns:
        List of (value1, value2) tuples for all valid pairs
    """
    result = []
    left = 0
    right = len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            result.append((numbers[left], numbers[right]))
            
            # Skip duplicates on both sides
            left_val = numbers[left]
            right_val = numbers[right]
            
            while left < right and numbers[left] == left_val:
                left += 1
            while left < right and numbers[right] == right_val:
                right -= 1
                
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return result
 
 
# Test
print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]  (1-indexed)
print(two_sum_sorted([2, 3, 4], 6))        # [1, 3]  (2 + 4 = 6)
 
# All pairs
print(two_sum_all_pairs([1, 1, 2, 2, 3, 3], 4))  # [(1, 3), (2, 2)]

Step-by-Step: [2, 3, 5, 8, 11, 15], target = 13
Step	Left	Right	Values	Sum	Action
1	0	5	(2, 15)	17	Too large → right--
2	0	4	(2, 11)	13	Found!

Handling Duplicates

Extension: Three Sum Problem

Problem Statement: Given an array, find all unique triplets that sum to zero.

Example:

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

This is a natural extension of two-sum: fix one element, then use two-pointer to find pairs that sum to the negation of the fixed element.

Approach:

Sort the array
For each element nums[i], find pairs in nums[i+1:] that sum to -nums[i]
Use converging two-pointer for the pair finding
Skip duplicates to avoid duplicate triplets

three_sum.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
def three_sum(nums: list[int]) -> list[list[int]]:
    """
    Find all unique triplets that sum to zero.
    
    Time: O(n²) - for each of n elements, O(n) two-pointer
    Space: O(1) extra space (output not counted)
    
    Key insight: Reduce 3-sum to multiple 2-sum problems.
    Fix one element, two-pointer the rest.
    """
    nums.sort()  # Sort for two-pointer to work
    result = []
    n = len(nums)
    
    for i in range(n - 2):  # Leave room for two more elements
        # Optimization: if smallest element > 0, no solution possible
        if nums[i] > 0:
            break
        
        # Skip duplicates for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        # Two-pointer for the remaining array
        target = -nums[i]  # Find pairs that sum to -nums[i]
        left = i + 1
        right = n - 1
        
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                
                # Skip duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                
                left += 1
                right -= 1
                
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return result
 
 
def three_sum_closest(nums: list[int], target: int) -> int:
    """
    Variant: Find the triplet sum closest to target.
    
    Same approach, but track the closest sum instead of exact match.
    """
    nums.sort()
    n = len(nums)
    closest = float('inf')
    
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            
            # Update closest if this sum is nearer
            if abs(current_sum - target) < abs(closest - target):
                closest = current_sum
            
            if current_sum == target:
                return target  # Can't get closer than exact match
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return closest
 
 
# Test
print(three_sum([-1, 0, 1, 2, -1, -4]))
# Output: [[-1, -1, 2], [-1, 0, 1]]
 
print(three_sum_closest([-1, 2, 1, -4], 1))
# Output: 2 (the triplet [-1, 2, 1] sums to 2)

Four Sum and Beyond

Classic Problem: Container With Most Water

Problem Statement: Given an array of heights representing vertical lines, find two lines that, together with the x-axis, form a container that holds the most water.

Example:

Input:  heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
        (Using lines at indices 1 and 8, heights 8 and 7, width 7)
        Area = min(8, 7) × 7 = 49

Key Insight:

Water is limited by the shorter of the two lines. Area = min(height[left], height[right]) × (right - left).

Brute force checks all pairs: O(n²). But with two pointers, we achieve O(n).

Why Two-Pointer Works Here:

Start with widest possible container (left = 0, right = n-1). The width is maximized.

At each step, we move the pointer at the shorter line. Why?

Area = min(heights[left], heights[right]) × width
If heights[left] < heights[right], moving right left cannot increase area:
- Width decreases
- The limiting factor (heights[left]) stays the same or its partner gets smaller
Therefore, we eliminate this left position and try a taller one

This greedy choice is correct because moving the shorter pointer is the only way to potentially increase area.

container_water.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def max_area(height: list[int]) -> int:
    """
    Find the maximum water container formed by two lines.
    
    Time: O(n) - single pass with two pointers
    Space: O(1) - only two pointers
    
    Args:
        height: Array of line heights
    
    Returns:
        Maximum water that can be contained
    """
    left = 0
    right = len(height) - 1
    max_water = 0
    
    while left < right:
        # Calculate current container's area
        width = right - left
        h = min(height[left], height[right])
        current_area = width * h
        max_water = max(max_water, current_area)
        
        # Move the pointer at the shorter line
        # Only moving the shorter one can potentially increase area
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water
 
 
def max_area_verbose(height: list[int]) -> int:
    """Same algorithm with detailed tracing."""
    left = 0
    right = len(height) - 1
    max_water = 0
    
    print(f"Heights: {height}")
    print("=" * 50)
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        current_area = width * h
        
        print(f"left={left} (h={height[left]}), right={right} (h={height[right]})")
        print(f"  Width={width}, Height=min({height[left]},{height[right]})={h}")
        print(f"  Area={current_area}, Max so far={max(max_water, current_area)}")
        
        max_water = max(max_water, current_area)
        
        if height[left] < height[right]:
            print(f"  Moving left (shorter) from {left} to {left+1}")
            left += 1
        else:
            print(f"  Moving right from {right} to {right-1}")
            right -= 1
        print()
    
    return max_water
 
 
# Test
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(f"Maximum area: {max_area(heights)}")  # 49
 
# Detailed trace with smaller example
max_area_verbose([1, 8, 6, 2, 5])

Don't Confuse with Trapping Rain Water

Classic Problem: Valid Palindrome

Problem Statement: Given a string, determine if it's a palindrome, considering only alphanumeric characters and ignoring case.

Example:

Input:  "A man, a plan, a canal: Panama"
Output: true  ("amanaplanacanalpanama" is a palindrome)

Palindrome checking is a natural fit for converging pointers: compare characters from both ends, moving inward.

valid_palindrome.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
def is_palindrome(s: str) -> bool:
    """
    Check if string is a palindrome (alphanumeric only, case-insensitive).
    
    Time: O(n) - single pass
    Space: O(1) - no extra string created
    """
    left = 0
    right = len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        
        # Skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1
        
        # Compare characters (case-insensitive)
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True
 
 
def is_palindrome_number(x: int) -> bool:
    """
    Check if an integer is a palindrome (without converting to string).
    
    Trick: Reverse half the number and compare.
    E.g., 12321 -> compare 123 and 12 (after reversing half)
    """
    # Negative numbers and numbers ending in 0 (except 0) aren't palindromes
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    
    reversed_half = 0
    
    # Build reversed second half
    while x > reversed_half:
        reversed_half = reversed_half * 10 + x % 10
        x //= 10
    
    # For odd-length: middle digit is in reversed_half, divide by 10 to ignore
    return x == reversed_half or x == reversed_half // 10
 
 
def valid_palindrome_ii(s: str) -> bool:
    """
    Can we make the string a palindrome by removing at most ONE character?
    
    LeetCode 680: Valid Palindrome II
    
    Strategy: Use two pointers, when mismatch found, try skipping either char.
    """
    def is_palindrome_range(s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
    
    left = 0
    right = len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            # Try skipping left char or right char
            return (is_palindrome_range(s, left + 1, right) or 
                    is_palindrome_range(s, left, right - 1))
        left += 1
        right -= 1
    
    return True
 
 
# Tests
print(is_palindrome("A man, a plan, a canal: Panama"))  # True
print(is_palindrome("race a car"))                       # False
 
print(is_palindrome_number(121))    # True
print(is_palindrome_number(-121))   # False
print(is_palindrome_number(10))     # False
 
print(valid_palindrome_ii("abca"))  # True (remove 'c' or 'b')
print(valid_palindrome_ii("abc"))   # False

Palindrome Variations

Reversing Arrays and Strings In-Place

One of the simplest applications of converging pointers is in-place reversal. Swap elements from both ends, moving inward until the pointers meet.

This pattern is a building block for more complex algorithms:

Rotating arrays (reverse parts, then reverse whole)
Reversing words in a sentence
Reversing linked lists (conceptually similar)

reverse_in_place.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
def reverse_array(arr: list) -> None:
    """
    Reverse array in-place using two pointers.
    
    Time: O(n) - n/2 swaps
    Space: O(1) - in-place
    """
    left = 0
    right = len(arr) - 1
    
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
 
 
def reverse_string(s: list[str]) -> None:
    """
    Reverse string (given as list of characters) in-place.
    
    Note: In Python, strings are immutable, so we work with char list.
    """
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
 
 
def reverse_words(s: list[str]) -> None:
    """
    Reverse words in a string in-place.
    
    Example: "hello world" -> "world hello"
    
    Strategy:
    1. Reverse entire string: "dlrow olleh"
    2. Reverse each word: "world hello"
    """
    def reverse_range(arr, left, right):
        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    
    n = len(s)
    
    # Step 1: Reverse entire string
    reverse_range(s, 0, n - 1)
    
    # Step 2: Reverse each word
    start = 0
    for i in range(n + 1):
        if i == n or s[i] == ' ':
            reverse_range(s, start, i - 1)
            start = i + 1
 
 
def rotate_array(nums: list[int], k: int) -> None:
    """
    Rotate array to the right by k steps in-place.
    
    Example: [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]
    
    Strategy: Three reverses
    1. Reverse all: [7,6,5,4,3,2,1]
    2. Reverse first k: [5,6,7,4,3,2,1]
    3. Reverse rest: [5,6,7,1,2,3,4]
    """
    def reverse_range(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
    
    n = len(nums)
    k = k % n  # Handle k > n
    
    reverse_range(0, n - 1)      # Reverse all
    reverse_range(0, k - 1)       # Reverse first k
    reverse_range(k, n - 1)       # Reverse remaining
 
 
# Tests
arr = [1, 2, 3, 4, 5]
reverse_array(arr)
print(arr)  # [5, 4, 3, 2, 1]
 
chars = list("hello world")
reverse_words(chars)
print(''.join(chars))  # "world hello"
 
nums = [1, 2, 3, 4, 5, 6, 7]
rotate_array(nums, 3)
print(nums)  # [5, 6, 7, 1, 2, 3, 4]

The Triple Reverse Trick

Problem: Squares of a Sorted Array

Problem Statement: Given an array sorted in non-decreasing order, return an array of the squares of each number, also in non-decreasing order.

Example:

Input:  [-4, -1, 0, 3, 10]
Output: [0, 1, 9, 16, 100]

Challenge: With negative numbers, simply squaring and keeping order doesn't work:

(-4)² = 16, (-1)² = 1, 0² = 0, 3² = 9, 10² = 100
Naive squares: [16, 1, 0, 9, 100] - not sorted!

Two-Pointer Insight:

After squaring, the largest values come from either end (most negative or most positive). Use converging pointers to build the result from the largest to smallest.

sorted_squares.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def sorted_squares(nums: list[int]) -> list[int]:
    """
    Return squares of sorted array in non-decreasing order.
    
    Time: O(n) - single pass with two pointers
    Space: O(n) - for result array
    
    Key insight: Largest squares are at the ends (most negative or positive).
    Build result from end to start.
    """
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1
    pos = n - 1  # Fill from end
    
    while left <= right:
        left_sq = nums[left] ** 2
        right_sq = nums[right] ** 2
        
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
        
        pos -= 1
    
    return result
 
 
def sorted_squares_verbose(nums: list[int]) -> list[int]:
    """Same algorithm with step-by-step trace."""
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1
    pos = n - 1
    
    print(f"Input: {nums}")
    print(f"Result size: {n}, filling from position {pos}")
    print()
    
    while left <= right:
        left_sq = nums[left] ** 2
        right_sq = nums[right] ** 2
        
        print(f"left={left} ({nums[left]}²={left_sq}), right={right} ({nums[right]}²={right_sq})")
        
        if left_sq > right_sq:
            print(f"  Left square larger, result[{pos}] = {left_sq}")
            result[pos] = left_sq
            left += 1
        else:
            print(f"  Right square larger/equal, result[{pos}] = {right_sq}")
            result[pos] = right_sq
            right -= 1
        
        pos -= 1
        print(f"  Result so far: {result}")
        print()
    
    return result
 
 
# Test
nums = [-4, -1, 0, 3, 10]
print(sorted_squares_verbose(nums))

Why we use left <= right here:

Unlike pair-finding where we need two distinct elements, here we're processing every element once. The condition left <= right ensures we process the final element when both pointers meet.

Summary: Opposite-Direction Pointers

You've now mastered the converging two-pointer pattern. Let's consolidate the key insights:

Key Takeaways

•Start at opposite ends — One pointer at start, one at end. Move based on comparison outcomes.
•Each move eliminates many candidates — This is why O(n²) pair searches become O(n).
•Sorted data unlocks this pattern — The ordering is what makes intelligent movement possible.
•Two-sum generalizes to k-sum — Nest loops for k-sum; innermost uses two-pointer.
•Container/optimization problems — Move the pointer that limits the objective (shortest line, etc.).
•Palindrome checking — Natural fit: compare from both ends.
•In-place reversal — Swap from ends, move inward. Foundation for rotations and word reversal.

Converging Two-Pointer Problem Types
Problem Type	Left Movement	Right Movement	Termination
Two sum (sorted)	sum < target	sum > target	Pointers meet or solution found
Container water	height[left] < height[right]	height[left] >= height[right]	Pointers meet
Palindrome check	After comparing	After comparing	Pointers meet or mismatch
In-place reverse	Always	Always	Pointers meet
Sorted squares	left² > right²	left² <= right²	Pointers cross

What's next:

Page Complete

You now have deep command of opposite-direction two-pointer techniques. These patterns form the foundation for pair-finding, optimization, and symmetry-checking algorithms.

3 / 5