Cracking the Coding Interview: Part 3 – The Two Pointer Technique

Cracking the Coding Interview: Part 3 – The Two Pointer Technique

In Part 2 of this series, we discussed the Sliding Window pattern, which helps efficiently solve problems involving contiguous subarrays or substrings. In Part 3, we’ll explore another fundamental pattern in coding interviews: the Two Pointer Technique. This technique is particularly effective for problems involving arrays, linked lists, or strings where comparisons or pairing elements are key.

Before we begin, if you’re looking for a comprehensive guide to prepare for coding interviews, consider checking out Cracking the Coding Interview, a must-have book for anyone serious about landing a job at top tech companies.

Overview of the Two Pointer Technique

The Two Pointer technique is a simple yet powerful method where two pointers (or indices) are used to iterate through data structures, typically in opposite directions or moving at different speeds. This pattern is particularly useful for problems involving:

• Pairing elements
• Searching for combinations (like two numbers that sum to a target)
• Comparing elements from two ends of an array or list
• Detecting cycles or palindromes

By moving two pointers simultaneously, this approach reduces the need for nested loops, transforming brute-force solutions into more efficient ones with time complexity as low as O(n).

When to Use the Two Pointer Technique:

• The input is sorted (or can be sorted).
• You need to find pairs of elements (e.g., pair of numbers adding up to a target).
• You need to detect or compare properties between elements (e.g., palindrome checking, linked list cycles).
• The problem can be divided into two subproblems (like searching from both ends of an array).

Types of Two Pointer Approaches

1. Two Pointers in Opposite Directions

What it is: Two pointers start from opposite ends of an array or list, moving toward each other to meet in the middle.

Example Problem: Given a sorted array, find two numbers that add up to a specific target.

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

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

        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Move the left pointer to the right.
        else:
            right -= 1  # Move the right pointer to the left.

    return []  # Return an empty list if no pair is found.

Explanation:

• The pointers start from both ends of the array.
• If the sum of the two elements at the pointers is smaller than the target, move the left pointer to the right (to increase the sum).
• If the sum is larger, move the right pointer to the left (to decrease the sum).
• This reduces a potential O(n²) brute-force search to O(n).

2. Two Pointers in the Same Direction

What it is: Both pointers move in the same direction, but at different speeds. This is useful for problems like detecting cycles, such as in linked lists, or for finding specific conditions in a sequence.

Example Problem: Detect a cycle in a linked list (Floyd’s Tortoise and Hare algorithm).

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def has_cycle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next  # Move slow pointer by 1 step.
        fast = fast.next.next  # Move fast pointer by 2 steps.

        if slow == fast:
            return True  # Cycle detected.

    return False  # No cycle detected.

Explanation:

• The slow pointer moves one step at a time, while the fast pointer moves two steps.
• If there’s a cycle, the fast pointer will eventually catch up with the slow pointer.
• This reduces the cycle detection problem from O(n²) to O(n).

Steps to Implement Two Pointer Solutions

1. Initialize the pointers: Typically, this involves starting one pointer at the beginning and the other at the end (for opposite direction) or both at the start (for same direction).

2. Define conditions: The movement of the pointers depends on the problem. Determine when to move each pointer and in which direction based on the current state of the solution.

3. Update results: At each step, check the condition you're optimizing for (e.g., sum, comparison). Update the result accordingly.

4. Stop condition: The loop continues until the two pointers either meet or cross each other (opposite direction), or a valid condition is satisfied (same direction).

Common Interview Questions Using the Two Pointer Technique

1. Two Sum (Sorted Array)

Problem: Given a sorted array of integers, find two numbers that add up to a given target.

Solution: Use two pointers from the start and end of the array, adjusting the pointers based on the sum.

2. Container With Most Water

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

Pattern: Use two pointers at both ends of the array. Move the pointer with the smaller height inward to maximize the area.

3. Palindrome Checking

Problem: Given a string, determine if it is a palindrome.

Pattern: Use two pointers, one at the start and one at the end of the string, moving inward while comparing characters.

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False  # Characters do not match.
        left += 1
        right -= 1

    return True  # All characters matched, so it's a palindrome.

Two Pointer Hacks for Interviews

• Start with a sorted array: Sorting the array allows for much easier two-pointer implementation, especially in pairing problems like Two Sum.
• Think in terms of comparisons: Whether it’s comparing characters in a string or elements in an array, always check what condition should move each pointer.
• Visualize with brute force: Begin by considering a brute-force solution, then look for patterns that two pointers can exploit to avoid unnecessary comparisons.
• Check bounds carefully: Be mindful of edge cases, especially when pointers meet or overlap.

Conclusion

The Two Pointer technique is a highly efficient method for solving a variety of coding interview problems, especially those involving comparisons, pairs, or cycles in sequences. By mastering this technique, along with the Sliding Window pattern, you’ll be well-equipped to handle many interview scenarios.

In the next part of this series, we’ll explore another essential pattern in coding interviews: The Fast and Slow Pointer Technique, which is particularly useful for detecting cycles and finding middle elements.

Stay tuned for Part 4!