DSA Interview Prep · Lesson

Two Pointers: Opposite Ends

Use left and right pointers moving toward each other to solve pair-sum in sorted arrays, valid palindrome, and trapping rain water.

The Two-Pointer Idea

The two-pointer technique uses two index variables that move toward each other (or in the same direction) to reduce the need for nested loops. Instead of checking every pair in O(n²), you make progress with each comparison and finish in O(n). It almost always requires the array to be sorted first, because sorting lets you reason about which direction to move each pointer based on whether the current pair sum is too large or too small.

# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left, right]
        elif s < target: left  += 1
        else:           right -= 1
    return []

Two-Sum in a Sorted Array

With a sorted array, place one pointer at the left end (smallest) and one at the right end (largest). If the sum is too small, move the left pointer right to increase it. If the sum is too large, move the right pointer left to decrease it. Each iteration advances at least one pointer, so the loop runs at most n times: O(n) total after the sort. Importantly, each move is provably correct because of the sorted ordering.

def two_sum_sorted(numbers, target):
    # numbers is 1-indexed per LeetCode 167
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]  # 1-indexed
        elif s < target:
            left  += 1  # need larger sum
        else:
            right -= 1  # need smaller sum
    return []

print(two_sum_sorted([2, 7, 11, 15], 9))   # [1, 2]
print(two_sum_sorted([2, 3, 4], 6))         # [1, 3]

All lessons in this course

← Back to DSA Interview Prep