Advanced

Two Pointers Advanced

These are the harder two-pointer problems that appear in top-tier coding interviews. Each requires a creative twist on the basic pattern — three pointers, greedy decisions, or stack-like simulation.

Problem 1: 3Sum (LeetCode 15)

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

Example: nums = [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]

def three_sum(nums: list[int]) -> list[list[int]]:
    """Find all unique triplets that sum to zero.

    Sort + fix one element + two pointers on the rest.
    Time: O(n^2), Space: O(1) excluding output
    """
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        # Skip duplicates for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        # Early termination: if smallest possible sum > 0, stop
        if nums[i] > 0:
            break

        left, right = i + 1, len(nums) - 1
        target = -nums[i]

        while left < right:
            current = nums[left] + nums[right]

            if current == 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 < target:
                left += 1
            else:
                right -= 1

    return result


# Test
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 1, 1]) == []
assert three_sum([0, 0, 0]) == [[0, 0, 0]]
print("All tests passed!")
✅
Duplicate Handling: The key to 3Sum is handling duplicates correctly. Skip duplicate values for each pointer position after finding a valid triplet. Sorting first makes this possible.

Problem 2: Trapping Rain Water (LeetCode 42)

Problem: Given n non-negative integers representing an elevation map, compute how much water it can trap after raining.

Example: height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6

def trap(height: list[int]) -> int:
    """Calculate trapped rainwater using two pointers.

    Key insight: water at position i = min(max_left, max_right) - height[i].
    Two pointers avoid precomputing max arrays.
    Time: O(n), Space: O(1)
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water


# Test
assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap([4, 2, 0, 3, 2, 5]) == 9
assert trap([]) == 0
assert trap([1]) == 0
print("All tests passed!")

Why two pointers work here: Water at any position depends on the minimum of the max heights to its left and right. If left_max ≤ right_max, we know the water at the left pointer is determined by left_max regardless of what lies between the pointers. So we can safely process the left side.

Problem 3: Sort Colors / Dutch National Flag (LeetCode 75)

Problem: Sort an array containing only 0, 1, and 2 in-place in a single pass.

Example: nums = [2,0,2,1,1,0] → [0,0,1,1,2,2]

def sort_colors(nums: list[int]) -> None:
    """Sort array of 0s, 1s, 2s in-place (Dutch National Flag).

    Three pointers: low (boundary for 0s), mid (scanner), high (boundary for 2s).
    Time: O(n), Space: O(1)
    """
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Don't increment mid: swapped element needs inspection


# Test
nums1 = [2, 0, 2, 1, 1, 0]
sort_colors(nums1)
assert nums1 == [0, 0, 1, 1, 2, 2]

nums2 = [2, 0, 1]
sort_colors(nums2)
assert nums2 == [0, 1, 2]

nums3 = [0]
sort_colors(nums3)
assert nums3 == [0]
print("All tests passed!")
💡
ML Application: The Dutch National Flag algorithm is used in quicksort's three-way partition (handling duplicate pivots) and in data preprocessing to separate categories — for example, splitting labeled training data into positive, neutral, and negative sentiment buckets.

Problem 4: Partition Labels (LeetCode 763)

Problem: Partition a string into as many parts as possible so that each letter appears in at most one part. Return the sizes.

Example: s = "ababcbacadefegdehijhklij" → [9, 7, 8]

def partition_labels(s: str) -> list[int]:
    """Partition string so each letter appears in at most one part.

    Greedy: track last occurrence of each char, extend partition boundary.
    Time: O(n), Space: O(1) - at most 26 chars
    """
    # Find last occurrence of each character
    last = {c: i for i, c in enumerate(s)}

    partitions = []
    start = 0
    end = 0

    for i, c in enumerate(s):
        end = max(end, last[c])  # extend partition to include last occurrence

        if i == end:
            # Current position reaches the partition boundary
            partitions.append(end - start + 1)
            start = i + 1

    return partitions


# Test
assert partition_labels("ababcbacadefegdehijhklij") == [9, 7, 8]
assert partition_labels("eccbbbbdec") == [10]
assert partition_labels("abc") == [1, 1, 1]
print("All tests passed!")

Problem 5: Backspace String Compare (LeetCode 844)

Problem: Given two strings s and t where '#' means backspace, return true if they are equal when typed.

Example: s = "ab#c", t = "ad#c" → True (both become "ac")

def backspace_compare(s: str, t: str) -> bool:
    """Compare two strings with backspace characters using O(1) space.

    Process both strings from right to left, skipping backspaced chars.
    Time: O(n + m), Space: O(1)
    """
    def next_valid_index(string, index):
        """Find the next valid character index (skipping backspaces)."""
        skip = 0
        while index >= 0:
            if string[index] == '#':
                skip += 1
                index -= 1
            elif skip > 0:
                skip -= 1
                index -= 1
            else:
                break
        return index

    i = len(s) - 1
    j = len(t) - 1

    while i >= 0 or j >= 0:
        i = next_valid_index(s, i)
        j = next_valid_index(t, j)

        # Get the characters (or sentinel if exhausted)
        char_s = s[i] if i >= 0 else ""
        char_t = t[j] if j >= 0 else ""

        if char_s != char_t:
            return False

        i -= 1
        j -= 1

    return True


# Test
assert backspace_compare("ab#c", "ad#c") == True
assert backspace_compare("ab##", "c#d#") == True
assert backspace_compare("a#c", "b") == False
assert backspace_compare("a##c", "#a#c") == True
print("All tests passed!")
✅
O(1) Space Trick: Processing from right to left avoids needing a stack. When you see '#', increment a skip counter. When you see a regular character with skip > 0, skip it and decrement. This simulates the stack behavior in constant space.

Summary

ProblemTechniqueTimeSpace
3SumSort + fix + two pointersO(n²)O(1)
Trapping Rain WaterOpposite pointers + max trackingO(n)O(1)
Sort ColorsThree pointers (Dutch Flag)O(n)O(1)
Partition LabelsGreedy + last occurrenceO(n)O(1)
Backspace CompareReverse traversal + skip counterO(n+m)O(1)