Two Pointers

Use two indices (L and R) scanning from opposite ends or at different speeds. Converts O(n²) brute-force pair checks into O(n) for sorted arrays.

// When to Use

Sorted array + find pair/triplet summing to target. Palindrome validation. Merging sorted arrays. Container/water problems with heights.

Easy Valid Palindrome

INSIGHT: Skip non-alphanumeric characters. Compare characters from both ends towards center.

OPTIMAL — O(n) time · O(1) space

def isPalindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum(): l += 1
        while l < r and not s[r].isalnum(): r -= 1
        if s[l].lower() != s[r].lower():
            return False
        l += 1; r -= 1
    return True

Medium 3Sum

INSIGHT: Sort the array. Fix one element, then use two pointers to find the pair. Skip duplicates to avoid repeated triplets.

BRUTE — O(n³)

def threeSum(nums):
    result = []
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                if nums[i]+nums[j]+nums[k] == 0:
                    result.append(sorted([nums[i],nums[j],nums[k]]))
    return [list(t) for t in set(map(tuple, result))]

OPTIMAL — O(n²)

def threeSum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]: continue  # skip dup
        l, r = i + 1, len(nums) - 1
        while l < r:
            total = nums[i] + nums[l] + nums[r]
            if total == 0:
                result.append([nums[i], nums[l], nums[r]])
                while l < r and nums[l] == nums[l+1]: l += 1
                while l < r and nums[r] == nums[r-1]: r -= 1
                l += 1; r -= 1
            elif total < 0: l += 1
            else: r -= 1
    return result

Medium Container With Most Water

INSIGHT: Water = min(h[l], h[r]) × (r-l). Always move the shorter wall inward — moving the taller side can never increase min height but always decreases width.

OPTIMAL — O(n) time · O(1) space

def maxArea(height):
    l, r = 0, len(height) - 1
    max_water = 0
    while l < r:
        water = min(height[l], height[r]) * (r - l)
        max_water = max(max_water, water)
        if height[l] < height[r]: l += 1  # move shorter wall
        else: r -= 1
    return max_water

Hard Trapping Rain Water

INSIGHT: Water at i = min(maxLeft, maxRight) - height[i]. Two pointers: process whichever side has the smaller max — that side's water level is determined.

BRUTE — O(n²)

def trap(height):
    total = 0
    for i in range(len(height)):
        left_max = max(height[:i+1])
        right_max = max(height[i:])
        total += min(left_max, right_max) - height[i]
    return total

OPTIMAL — O(n) time · O(1) space

def trap(height):
    l, r = 0, len(height) - 1
    left_max = right_max = 0
    total = 0
    while l < r:
        if height[l] <= height[r]:
            left_max = max(left_max, height[l])
            total += left_max - height[l]
            l += 1
        else:
            right_max = max(right_max, height[r])
            total += right_max - height[r]
            r -= 1
    return total

← Arrays & Hashing Sliding Window →