Coding Patterns - Two-Pointer Technique

Intuition

The two-pointer technique is an algorithm strategy where two indices move through a data structure (like an array or linked list). A single pointer tracks one spot, but with two you can compare positions and solve problems more efficiently. Instead of nested loops that take O(n²) time, two pointers often reduce the work to O(n). That’s why it’s a favorite in coding interviews and real-world problems.

Two-Pointer Strategies

Two-pointer algorithms usually work in linear time O(n). Here are the three main strategies:

1. Inward Traversal

• Pointers start at opposite ends of the array and move toward each other.

• Useful for problems like pair sums, palindrome checks, or container problems.

2. Unidirectional Traversal

• Both pointers start at the same end and move forward.

• Often used when one pointer scans ahead while the other tracks processed data (e.g., shifting elements).

3. Staged Traversal

• One pointer traverses, and when it finds a specific condition, the second pointer takes over.

• Common in problems like partitioning or next lexicographical arrangements.

When To Use Two Pointers

Use two pointers when:

• The data structure is linear (array or linked list).

• The input follows predictable dynamics (like sorted arrays).

• The problem involves comparing pairs of elements, finding sums, or validating symmetry (palindromes).

Inward Traversal

Inward traversal is one of the most common uses of the two-pointer technique. Here, two pointers are placed at the opposite ends of a data structure (usually an array or string) and move toward each other. The process continues until they either meet or cross paths. This strategy is powerful when problems involve comparing or summing elements from both ends.

Example Problems

• Pair Sum in Sorted Array: Check if two numbers add up to a given target.

• Triplet Sum: Extend the idea to three numbers using a fixed element plus two pointers.

• Container With Most Water: Calculate maximum area formed between two heights.

• Palindrome Check: Compare characters from both ends toward the center.

Coding Example: Pair Sum in Sorted Array

def pair_sum(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        curr_sum = arr[left] + arr[right]
        if curr_sum == target:
            return True
        elif curr_sum < target:
            left += 1
        else:
            right -= 1
    return False

# Example usage
print(pair_sum([1, 3, 4, 6, 8, 10], 14))  # True (4 + 10)

Key Insight

The inward traversal method leverages the sorted nature of data. If the sum is too small, you move the left pointer rightward; if too large, move the right pointer leftward. This removes the need for nested loops.

Practice Exercise

Write a function to check if a given string is a palindrome using inward traversal.

Solution:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("level"))  # True
print(is_palindrome("hello"))  # False

Unidirectional Traversal

In unidirectional traversal, both pointers start from the same end (usually the beginning) and move forward together. Each pointer has a distinct role—one scans the input to discover new information, while the other maintains a processed region or writes results in-place. This pattern shines when we must filter, compact, or rearrange elements while keeping operations linear and memory-efficient.

Example Problems

• Shift Zeros to the End: Maintain the relative order of non-zeros while moving all zeros to the end in-place.

• Remove Duplicates from Sorted Array: Keep only unique elements and return the new logical length.

• Partition by Predicate: Move elements that satisfy a condition to the front (e.g., evens before odds) while scanning once.

Coding Example: Shift Zeros to the End (Stable, In‑Place)

def move_zeros(nums):
    write = 0  # Points to the next position to write a non-zero
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write] = nums[read]
            write += 1
    # Fill the remainder with zeros
    while write < len(nums):
        nums[write] = 0
        write += 1
    return nums

# Example usage
print(move_zeros([0, 1, 0, 3, 12]))  # [1, 3, 12, 0, 0]

Key Insight

Use one pointer (read) to inspect every element and another (write) to commit valid results. This preserves stability (relative order) and avoids extra memory.

Practice Exercise

Task: Implement remove_duplicates(nums) for a sorted array so that each element appears only once. Return the new length and modify nums in-place to have the unique elements at the start.

Solution:

def remove_duplicates(nums):
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write  # new logical length

arr = [0,0,1,1,1,2,2,3,3,4]
new_len = remove_duplicates(arr)
print(new_len, arr[:new_len])  # 5 [0, 1, 2, 3, 4]

Staged Traversal

Staged traversal is a slightly advanced variant of the two-pointer technique. Here, one pointer traverses the data structure, and when it encounters an element meeting a certain condition, a second pointer is activated to perform additional processing. This makes staged traversal useful when the problem requires layered decisions or grouping elements dynamically.

Example Problems

• Partitioning by Condition: Divide elements into groups (e.g., even vs odd, vowels vs consonants).

• Next Lexicographical Sequence: Identify a pivot element, then use a second pointer to adjust the suffix for the next permutation.

• Subsequence Matching: Use one pointer to scan the main string and the other to track a smaller subsequence.

Coding Example: Next Lexicographical Permutation

def next_permutation(nums):
    # Step 1: Find pivot index
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1

    if i >= 0:
        # Step 2: Find rightmost element greater than pivot
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        # Swap pivot with j
        nums[i], nums[j] = nums[j], nums[i]

    # Step 3: Reverse suffix
    nums[i + 1:] = reversed(nums[i + 1:])
    return nums

# Example usage
print(next_permutation([1, 2, 3]))  # [1, 3, 2]

Key Insight

The first pointer identifies a trigger point (pivot, condition, or match), and the second pointer performs an operation relative to it (swap, partition, or comparison). This staged responsibility simplifies complex tasks into predictable sub-steps.

Practice Exercise

Task: Write a function that checks if a sequence s is a subsequence of another string t using staged traversal.

Solution:

def is_subsequence(s, t):
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

print(is_subsequence("abc", "ahbgdc"))  # True
print(is_subsequence("axc", "ahbgdc"))  # False

Key Takeaways

The two-pointer technique is a cornerstone strategy in algorithm design. By maintaining two indices and moving them intelligently, we can transform problems that normally require nested loops into linear-time solutions. Throughout this chapter, we explored three major strategies:

1. Inward Traversal

   • Pointers start at opposite ends and move toward each other.

   • Useful for pair sums, palindrome checks, and container problems.

2. Unidirectional Traversal

   • Both pointers start from the same end and move forward.

   • Ideal for filtering, compaction, and removing duplicates in arrays.

3. Staged Traversal

   • One pointer scans, the other activates on a condition.

   • Useful for partitioning, subsequence matching, and permutations.

Key Insights

• Two pointers often reduce time complexity from O(n^2) to O(n).

• Sorted arrays or predictable data structures maximize efficiency.

• Choosing how pointers move (inward, forward, or staged) depends on the problem’s structure.

Next Chapter