Two Pointers Technique

Generated on 2025-07-10 02:07:14 Algorithm Cheatsheet for Technical Interviews

Two Pointers Technique Cheatsheet

1. Quick Overview

The Two Pointers technique is an algorithm design paradigm where you use two pointers to iterate through a data structure (usually an array or linked list) in a coordinated manner. It’s especially useful for problems that involve searching for pairs, triplets, or sub-arrays that satisfy certain conditions.

When to use:

Sorted arrays/lists
Searching for pairs/triplets
Reversing arrays/strings in-place
Sliding window problems (one pointer defines the start, another the end)
Generally, when needing to compare elements within a single array or list.

2. Time & Space Complexity

Time Complexity: Often O(N) or O(N log N) if sorting is involved. Can sometimes be O(N²) if nested loops are unavoidable, but you strive to avoid this.
Space Complexity: Usually O(1) (constant) if done in-place. Can be O(log N) or O(N) if sorting or recursion is used, depending on the algorithm.

3. Implementation

Here are basic examples of a two-pointer approach in Python, Java, and C++:

Python:

def two_pointers(arr, target):
    """
    Finds if there are two numbers in a sorted array that sum up to the target.

    Args:
        arr: A sorted array of integers.
        target: The target sum.

    Returns:
        True if a pair exists, False otherwise.
    """
    left = 0
    right = len(arr) - 1

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

        if current_sum == target:
            return True  # Found a pair

        elif current_sum < target:
            left += 1  # Increase the sum

        else:
            right -= 1  # Decrease the sum

    return False  # No pair found

Java:

class TwoPointers {
    public static boolean twoPointers(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int currentSum = arr[left] + arr[right];

            if (currentSum == target) {
                return true; // Found a pair
            } else if (currentSum < target) {
                left++; // Increase the sum
            } else {
                right--; // Decrease the sum
            }
        }

        return false; // No pair found
    }
}

C++:

#include <vector>

bool twoPointers(std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) {
        int currentSum = arr[left] + arr[right];

        if (currentSum == target) {
            return true; // Found a pair
        } else if (currentSum < target) {
            left++; // Increase the sum
        } else {
            right--; // Decrease the sum
        }
    }

    return false; // No pair found
}

4. Common Patterns

Pattern	Description	Example Problem
Finding a Pair	Locate two elements that satisfy a condition (e.g., sum to a target).	Two Sum II - Input array is sorted
Reversing	Reverse a string, array, or linked list.	Reverse String
Sliding Window	Maintain a “window” of elements and move it across the data structure.	Maximum Sum Subarray of Size K
Fast & Slow Pointers	One pointer moves faster than the other. Useful for detecting cycles in linked lists.	Linked List Cycle
Merge Intervals	Merge overlapping intervals.	Merge Intervals

5. Pro Tips

Pre-Sorting: If the input array is not sorted, sorting it first (O(N log N)) might be necessary before applying the two-pointer technique.
Edge Cases: Handle empty arrays, arrays with one element, and cases where no solution exists.
Pointer Movement: Carefully consider the conditions for moving the pointers. Incorrect movement can lead to infinite loops or incorrect results.
Duplicate Handling: If the problem requires unique pairs, skip duplicate elements to avoid redundant calculations.
Off-by-One Errors: Pay attention to the loop termination condition (left < right vs. left <= right) and pointer increments/decrements.

6. Practice Problems

Two Sum II - Input array is sorted (LeetCode #167): Given a sorted array of integers, find two numbers such that they add up to a specific target number.
- Solution Approach: Use two pointers, one at the beginning and one at the end of the array. Move the pointers based on whether the current sum is greater or less than the target.
Remove Duplicates from Sorted Array (LeetCode #26): Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
- Solution Approach: Use two pointers, one to track the unique elements and another to iterate through the array.
3Sum (LeetCode #15): Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
- Solution Approach: Sort the array first. Iterate through the array and for each element, use the two-pointer technique to find two other elements that sum up to the negative of the current element.

7. Templates

These templates provide a reusable structure for common two-pointer scenarios.

Python Template:

def two_pointers_template(arr, condition):
    """
    Template for solving two-pointer problems.

    Args:
        arr: The input array.
        condition: A function that checks if the current pair/subset satisfies the condition.

    Returns:
        The result based on the problem's requirements.
    """
    left = 0
    right = len(arr) - 1

    while left < right:  # Or left <= right, depending on the problem
        # Perform operations using arr[left] and arr[right]

        if condition(arr[left], arr[right]):
            # Condition met, update result or move pointers accordingly
            return #or update the pointers and continue the loop if multiple solutions are needed
        elif arr[left] + arr[right] < target: #Example condition
            left += 1  # Adjust pointers based on the condition
        else:
            right -= 1

    return # Default return if no solution is found

Java Template:

class TwoPointersTemplate {
    public static <T> T twoPointersTemplate(int[] arr, Condition<Integer> condition) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) { // Or left <= right
            // Perform operations using arr[left] and arr[right]

            if (condition.test(arr[left], arr[right])) {
                // Condition met, update result or move pointers accordingly
                return (T)"result"; // Replace "result" with the actual result type and value
            } else if (arr[left] + arr[right] < 0) { //Example condition
                left++; // Adjust pointers based on the condition
            } else {
                right--;
            }
        }

        return (T) "default"; // Default return if no solution is found
    }

    interface Condition<T> {
        boolean test(T a, T b);
    }
}

C++ Template:

#include <vector>
#include <functional>

template <typename T>
T twoPointersTemplate(std::vector<int>& arr, std::function<bool(int, int)> condition) {
    int left = 0;
    int right = arr.size() - 1;

    while (left < right) { // Or left <= right
        // Perform operations using arr[left] and arr[right]

        if (condition(arr[left], arr[right])) {
            // Condition met, update result or move pointers accordingly
            return (T) 1; // Replace 1 with the actual result type and value
        } else if (arr[left] + arr[right] < 0) { //Example condition
            left++; // Adjust pointers based on the condition
        } else {
            right--;
        }
    }

    return (T) 0; // Default return if no solution is found
}

These templates are designed to be a starting point. Adapt them to the specific requirements of the problem you are solving. Remember to define the condition function appropriately for each use case. Good luck!