Intermediate

Two Pointers Basic

Two pointers is the simplest yet most powerful technique for sorted arrays and in-place operations. By maintaining two indices that move based on conditions, you eliminate nested loops and achieve O(n) time.

Problem 1: Two Sum II - Sorted Array (LeetCode 167)

Problem: Given a 1-indexed sorted array and a target, find two numbers that add up to target. Return their indices.

Example: numbers = [2,7,11,15], target = 9 → [1, 2]

def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
    """Find two numbers in sorted array that sum to target.

    Opposite-direction two pointers on sorted array.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1   # need a larger sum
        else:
            right -= 1  # need a smaller sum

    return []  # no solution found


# Test
assert two_sum_sorted([2, 7, 11, 15], 9) == [1, 2]
assert two_sum_sorted([2, 3, 4], 6) == [1, 3]
assert two_sum_sorted([-1, 0], -1) == [1, 2]
print("All tests passed!")
✅
Why it works: Since the array is sorted, if the sum is too small, moving left right increases it. If too large, moving right left decreases it. This covers all pairs without nested loops.

Problem 2: Container With Most Water (LeetCode 11)

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

Example: height = [1,8,6,2,5,4,8,3,7] → 49

def max_area(height: list[int]) -> int:
    """Find the container with most water.

    Greedy two pointers: always move the shorter line inward.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        # Water = width * min(height)
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        # Move the shorter line (it limits capacity)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water


# Test
assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert max_area([1, 1]) == 1
assert max_area([4, 3, 2, 1, 4]) == 16
print("All tests passed!")

Why move the shorter line? Moving the taller line can only decrease or maintain the height (since min determines water level), and the width decreases by 1. So the area can only decrease. Moving the shorter line might find a taller one, potentially increasing area.

Problem 3: Remove Duplicates from Sorted Array (LeetCode 26)

Problem: Remove duplicates in-place from a sorted array. Return the number of unique elements.

Example: nums = [0,0,1,1,1,2,2,3,3,4] → 5, nums = [0,1,2,3,4,...]

def remove_duplicates(nums: list[int]) -> int:
    """Remove duplicates from sorted array in-place.

    Same-direction two pointers: slow = write position, fast = read.
    Time: O(n), Space: O(1)
    """
    if not nums:
        return 0

    slow = 0  # points to last unique element

    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1


# Test
nums1 = [1, 1, 2]
assert remove_duplicates(nums1) == 2
assert nums1[:2] == [1, 2]

nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
assert remove_duplicates(nums2) == 5
assert nums2[:5] == [0, 1, 2, 3, 4]
print("All tests passed!")

Problem 4: Move Zeroes (LeetCode 283)

Problem: Move all zeroes to the end of the array while maintaining the relative order of non-zero elements. Do it in-place.

Example: nums = [0,1,0,3,12] → [1,3,12,0,0]

def move_zeroes(nums: list[int]) -> None:
    """Move all zeroes to end, maintaining order of non-zero elements.

    Same-direction two pointers with swap.
    Time: O(n), Space: O(1)
    """
    slow = 0  # position for next non-zero element

    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1


# Test
nums1 = [0, 1, 0, 3, 12]
move_zeroes(nums1)
assert nums1 == [1, 3, 12, 0, 0]

nums2 = [0]
move_zeroes(nums2)
assert nums2 == [0]

nums3 = [1, 0, 0, 0, 2]
move_zeroes(nums3)
assert nums3 == [1, 2, 0, 0, 0]
print("All tests passed!")
💡
Pattern Recognition: Problems 3 and 4 both use same-direction two pointers. The slow pointer marks where the next "valid" element should go, and fast scans through the array. This is the core partitioning pattern.

Problem 5: Valid Palindrome (LeetCode 125)

Problem: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example: s = "A man, a plan, a canal: Panama" → True

def is_palindrome(s: str) -> bool:
    """Check if string is a valid palindrome (alphanumeric only).

    Opposite-direction two pointers, skipping non-alphanumeric.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1

    while left < right:
        # Skip non-alphanumeric characters
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True


# Test
assert is_palindrome("A man, a plan, a canal: Panama") == True
assert is_palindrome("race a car") == False
assert is_palindrome(" ") == True
assert is_palindrome("ab_a") == True
print("All tests passed!")

Summary

ProblemPointer DirectionTimeSpace
Two Sum SortedOpposite (inward)O(n)O(1)
Container Most WaterOpposite (inward)O(n)O(1)
Remove DuplicatesSame directionO(n)O(1)
Move ZeroesSame directionO(n)O(1)
Valid PalindromeOpposite (inward)O(n)O(1)