Two Pointer

Comprehensive documentation for implementing the two pointer technique in algorithmic problem solving

Introduction

Two pointer technique is an algorithmic pattern that leverages two indices to traverse data structures efficiently, primarily used for optimization problems involving arrays and linked lists.

Most implementations require a sorted data structure for correct functionality. Time complexity includes O(n log n) for the sorting operation when required.

Implementation

Pattern 1: Opposite Direction Traversal

#include <stdlib.h>

typedef struct {
    int first;
    int second;
} Pair;

Pair* findTargetSum(int* numbers, int size, int target) {
    // Precondition: numbers must be sorted
    int left = 0;
    int right = size - 1;
    
    while (left < right) {
        int currentSum = numbers[left] + numbers[right];
        
        if (currentSum == target) {
            Pair* result = (Pair*)malloc(sizeof(Pair));
            result->first = numbers[left];
            result->second = numbers[right];
            return result;
        }
        
        if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return NULL;  // Return NULL if not found
}

// Don't forget to free the returned pair when done


template<typename T>
std::pair<T, T> findTargetSum(std::vector<T>& numbers, T target) {
    // Precondition: numbers must be sorted
    int left = 0;
    int right = numbers.size() - 1;
    
    while (left < right) {
        T currentSum = numbers[left] + numbers[right];
        
        if (currentSum == target) {
            return std::make_pair(numbers[left], numbers[right]);
        }
        
        if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return std::make_pair(T{}, T{});  // Return empty pair if not found
}

def find_target_sum(numbers: List[int], target: int) -> Optional[Tuple[int, int]]:
"""
Finds two numbers in a sorted array that sum to the target value.

Args:
    numbers: Sorted array of integers
    target: Target sum to find
    
Returns:
    Tuple of two numbers that sum to target, or None if not found
"""
left, right = 0, len(numbers) - 1

while left < right:
    current_sum = numbers[left] + numbers[right]
    if current_sum == target:
        return (numbers[left], numbers[right])
    elif current_sum < target:
        left += 1
    else:
        right -= 1
return None

function findTargetSum(numbers, target) {
let left = 0;
let right = numbers.length - 1;

while (left < right) {
    const currentSum = numbers[left] + numbers[right];
    
    if (currentSum === target) {
        return [numbers[left], numbers[right]];
    }
    
    if (currentSum < target) {
        left++;
    } else {
        right--;
    }
}
return null;
}

Pattern 2: Same Direction Traversal

Implementation Consideration

Same direction traversal requires careful boundary condition management to prevent pointer overlap or array out-of-bounds access.

#include <stdlib.h>

typedef struct {
    int first;
    int second;
} Pair;

Pair* findTargetSum(int* numbers, int size, int target) {
    // Precondition: numbers must be sorted
    int left = 0;
    int right = size - 1;
    
    while (left < right) {
        int currentSum = numbers[left] + numbers[right];
        
        if (currentSum == target) {
            Pair* result = (Pair*)malloc(sizeof(Pair));
            result->first = numbers[left];
            result->second = numbers[right];
            return result;
        }
        
        if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return NULL;  // Return NULL if not found
}

// Don't forget to free the returned pair when done

#include <vector>
using namespace std;

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;

    int writeIndex = 1;
    for (int readIndex = 1; readIndex < nums.size(); ++readIndex) {
        if (nums[readIndex] != nums[readIndex - 1]) {
            nums[writeIndex] = nums[readIndex];
            ++writeIndex;
        }
    }
    return writeIndex;
}

from typing import List

def remove_duplicates(array: List[int]) -> int:
    """
    Removes duplicates from a sorted array in-place.
    
    Args:
        array: Sorted array of integers
        
    Returns:
        Length of array after removing duplicates
    """
    if not array:
        return 0
        
    write_index = 1
    for read_index in range(1, len(array)):
        if array[read_index] != array[read_index - 1]:
            array[write_index] = array[read_index]
            write_index += 1
            
    return write_index

function removeDuplicates(nums) {
if (nums.length === 0) return 0;

let writeIndex = 1;
for (let readIndex = 1; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== nums[readIndex - 1]) {
        nums[writeIndex] = nums[readIndex];
        writeIndex++;
    }
}
return writeIndex;
}

Implementation Pattern

Input Validation

Implement robust input validation to handle edge cases such as empty arrays, single elements, and invalid inputs. Define clear preconditions and post conditions.

Pointer Initialization

Initialize pointers based on the traversal pattern required. Ensure initial positions are valid and maintain necessary invariants throughout execution.

Movement Logic

Define clear conditions for pointer movement. Implement boundary checks and ensure pointers maintain their relative positions according to the algorithm requirements.

Termination Conditions

Establish explicit termination conditions to prevent infinite loops. Include both success and failure conditions in the implementation.

Critical Considerations

Implement boundary checks for array access
Handle null/undefined inputs appropriately
Validate preconditions before execution
Consider thread safety in concurrent environments

Implementation Variants

Standard Two Pointer

def standard_pattern(array):
    left = 0
    right = len(array) - 1
    
    while left < right:
        # Process elements
        left += 1
        right -= 1

Fast-Slow Pointer

def fast_slow_pattern(array):
    slow = 0
    fast = 0
    
    while fast < len(array):
        # Process elements
        slow += 1
        fast += 2

Testing Strategy

Unit Tests

Implement comprehensive unit tests covering edge cases, boundary conditions, and typical usage patterns.

Integration Tests

Test interaction with sorting algorithms and data structure implementations.

Performance Tests

Validate time and space complexity requirements under various input conditions.

Common Applications

The two pointer technique is versatile and can be applied to solve various algorithmic problems efficiently:

Finding Pairs with Specific Sum

Used in problems like "Two Sum", where we need to find pairs of elements in a sorted array that sum to a target value.

# Time Complexity: O(n)
# Space Complexity: O(1)
def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]  # or [nums[left], nums[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []  # No pair found

Three Sum Problem

An extension of Two Sum, finding triplets that sum to a specific value.

# Time Complexity: O(n²)
# Space Complexity: O(1) excluding output array
def three_sum(nums, target=0):
    nums.sort()  # O(n log n)
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        # Skip duplicates for the first element
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total < target:
                left += 1
            elif total > target:
                right -= 1
            else:
                # Found a triplet
                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
                
    return result

Container With Most Water

Finding two lines that, together with the x-axis, form a container that holds the most water.

# Time Complexity: O(n)
# Space Complexity: O(1)
def max_area(height):
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        # Calculate water volume: width × min(height[left], height[right])
        water = (right - left) * min(height[left], height[right])
        max_water = max(max_water, water)
        
        # Move the pointer of smaller height inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
            
    return max_water

Removing Duplicates

In-place removal of duplicates from sorted arrays.

# Time Complexity: O(n)
# Space Complexity: O(1)
def remove_duplicates(nums):
    if not nums:
        return 0
        
    # Position to insert next unique element
    insert_index = 1
    
    for i in range(1, len(nums)):
        if nums[i] != nums[i - 1]:
            nums[insert_index] = nums[i]
            insert_index += 1
            
    return insert_index  # Length of the array without duplicates

Palindrome Verification

Checking if a string is a palindrome by comparing characters from both ends.

# Time Complexity: O(n)
# Space Complexity: O(1)
def is_palindrome(s):
    # Convert to lowercase and remove non-alphanumeric characters
    s = ''.join(c.lower() for c in s if c.isalnum())
    
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
        
    return True

The two pointer technique is particularly effective when dealing with sorted arrays, as it allows for linear time complexity without additional space requirements.

Complexity Analysis

Understanding the complexity of two-pointer algorithms is crucial for effective implementation:

Time Complexity

Pattern	Best Case	Average Case	Worst Case	Notes
Opposite Direction	O(1)	O(n)	O(n)	Best case occurs when the target is found immediately
Same Direction	O(n)	O(n)	O(n)	Typically requires a single pass through the data structure
Fast-Slow	O(n)	O(n)	O(n)	Useful for cycle detection and middle-finding problems
Sliding Window	O(n)	O(n)	O(n)	Window size varies based on problem constraints

When sorting is required before applying the two-pointer technique, the overall time complexity becomes O(n log n) due to the sorting operation.

Two pointer algorithms typically have O(1) space complexity, making them memory-efficient solutions for various problems. This constant space usage is one of the key advantages of this technique over alternative approaches that might require additional data structures.

The space complexity remains constant regardless of input size because:

Only a fixed number of pointers/variables are used
Operations are performed in-place on the original data structure
No recursive call stack is required
No additional data structures are needed to track state

Implementation Note

Some variations might require O(n) space for output storage (like collecting all valid pairs), but the algorithm's working space remains O(1).

Pattern 3: Sliding Window

The sliding window technique is a specialized form of two-pointer method that maintains a "window" between two pointers, typically expanding or contracting based on certain conditions.

Key Insight

Sliding Window optimizes solutions for subarray/substring problems by avoiding redundant computations when the window shifts.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int maxSubarraySum(int arr[], int n, int k) {
    // Find maximum sum subarray of length k
    if (n < k) {
        printf("Invalid input: Array length smaller than window size\n");
        return -1;
    }
    
    // Compute sum of first window
    int maxSum = 0;
    for (int i = 0; i < k; i++) {
        maxSum += arr[i];
    }
    
    // Compute sums of other windows by removing first element
    // of previous window and adding last element of current window
    int windowSum = maxSum;
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        if (windowSum > maxSum) {
            maxSum = windowSum;
        }
    }
    
    return maxSum;
}

// Function to find smallest subarray with sum greater than given value
int smallestSubarrayWithSum(int arr[], int n, int targetSum) {
    int minLength = INT_MAX;
    int windowSum = 0;
    int windowStart = 0;
    
    for (int windowEnd = 0; windowEnd < n; windowEnd++) {
        // Add the next element to the window
        windowSum += arr[windowEnd];
        
        // Shrink the window as small as possible while maintaining sum >= targetSum
        while (windowSum >= targetSum) {
            int currentLength = windowEnd - windowStart + 1;
            if (currentLength < minLength) {
                minLength = currentLength;
            }
            
            // Remove the starting element from the window
            windowSum -= arr[windowStart];
            windowStart++;
        }
    }
    
    // If no valid window found
    return minLength == INT_MAX ? 0 : minLength;
}

#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

// Fixed window size - maximum sum subarray of size k
int maxSubarraySum(const vector<int>& arr, int k) {
    if (arr.size() < k) return -1; // Invalid input
    
    // Sum first k elements
    int currentSum = 0;
    for (int i = 0; i < k; i++) {
        currentSum += arr[i];
    }
    
    int maxSum = currentSum;
    
    // Slide window: remove one element from left, add one from right
    for (int i = k; i < arr.size(); i++) {
        currentSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

// Dynamic window size - smallest subarray with sum >= targetSum
int smallestSubarrayWithSum(const vector<int>& arr, int targetSum) {
    int minLength = numeric_limits<int>::max();
    int windowSum = 0;
    int windowStart = 0;
    
    for (int windowEnd = 0; windowEnd < arr.size(); windowEnd++) {
        windowSum += arr[windowEnd]; // Expand window
        
        // Contract window when condition is met
        while (windowSum >= targetSum) {
            minLength = min(minLength, windowEnd - windowStart + 1);
            windowSum -= arr[windowStart];
            windowStart++;
        }
    }
    
    return minLength == numeric_limits<int>::max() ? 0 : minLength;
}

from typing import List

# Fixed window size - maximum sum subarray of size k
def max_subarray_sum(arr: List[int], k: int) -> int:
    """
    Find the maximum sum of a subarray of size k.
    
    Args:
        arr: Array of integers
        k: Size of the sliding window/subarray
        
    Returns:
        Maximum sum of any contiguous subarray of size k
    """
    n = len(arr)
    if n < k:
        return -1  # Invalid input
    
    # Compute sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum
    
    # Slide window from start to end in array
    for i in range(k, n):
        # Add next element and remove first element of previous window
        window_sum = window_sum + arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
        
    return max_sum

# Dynamic window size - smallest subarray with sum >= targetSum
def smallest_subarray_with_given_sum(arr: List[int], target_sum: int) -> int:
    """
    Find length of smallest contiguous subarray with sum at least target_sum.
    
    Args:
        arr: Array of positive integers
        target_sum: Minimum required sum
        
    Returns:
        Length of the smallest subarray with sum >= target_sum, 
        or 0 if no such subarray exists
    """
    window_start = 0
    window_sum = 0
    min_length = float('inf')
    
    for window_end in range(len(arr)):
        window_sum += arr[window_end]  # Add the next element
        
        # Shrink window as small as possible while maintaining the condition
        while window_sum >= target_sum:
            min_length = min(min_length, window_end - window_start + 1)
            window_sum -= arr[window_start]
            window_start += 1
            
    return min_length if min_length != float('inf') else 0

/**
 * Find the maximum sum of a contiguous subarray of size k
 * @param {number[]} arr - Array of numbers
 * @param {number} k - Window size
 * @returns {number} Maximum sum of any window
 */
function maxSubarraySum(arr, k) {
    if (arr.length < k) return null;
    
    // Initial window sum
    let maxSum = 0;
    let windowSum = 0;
    
    // First window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    maxSum = windowSum;
    
    // Slide window and calculate sums
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum + arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    
    return maxSum;
}

/**
 * Find length of smallest subarray with sum at least targetSum
 * @param {number[]} arr - Array of positive numbers
 * @param {number} targetSum - Target sum threshold
 * @returns {number} Length of smallest valid subarray or 0 if none
 */
function smallestSubarrayWithGivenSum(arr, targetSum) {
    let windowSum = 0;
    let minLength = Infinity;
    let windowStart = 0;
    
    for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
        // Add next element to window
        windowSum += arr[windowEnd];
        
        // Shrink window as much as possible while maintaining condition
        while (windowSum >= targetSum) {
            minLength = Math.min(minLength, windowEnd - windowStart + 1);
            windowSum -= arr[windowStart];
            windowStart++;
        }
    }
    
    return minLength === Infinity ? 0 : minLength;
}

The sliding window technique is most efficient for problems involving contiguous sequences and when operations can be performed incrementally as the window moves.

Pattern 4: Fast and Slow Pointers (Floyd's Cycle Detection)

This pattern uses two pointers moving at different speeds to identify cycles in linked lists or arrays.

#include <stdbool.h>

// Node definition for a singly linked list
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// Floyd's Cycle Detection Algorithm
bool hasCycle(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return false; // Empty list or single node cannot have a cycle
    }
    
    // Initialize slow and fast pointers
    ListNode* slow = head;
    ListNode* fast = head;
    
    // Move slow one step and fast two steps
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;        // Move one step
        fast = fast->next->next;  // Move two steps
        
        // If slow and fast meet, there's a cycle
        if (slow == fast) {
            return true;
        }
    }
    
    // If fast reaches the end, there's no cycle
    return false;
}

// Function to find the start of the cycle
ListNode* detectCycleStart(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return NULL; // No cycle
    }
    
    // Detect cycle
    ListNode* slow = head;
    ListNode* fast = head;
    bool hasCycle = false;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) {
        return NULL; // No cycle detected
    }
    
    // Find cycle start: reset slow to head and move both one step at a time
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow; // Meeting point is the start of the cycle
}

#include <iostream>

// Definition for singly-linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    // Detect if there's a cycle
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                return true; // Cycle detected
            }
        }
        
        return false; // No cycle
    }
    
    // Find the node where cycle begins
    ListNode *detectCycleStart(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }
        
        // Phase 1: Detect cycle
        ListNode *slow = head;
        ListNode *fast = head;
        bool hasCycle = false;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        if (!hasCycle) {
            return nullptr;
        }
        
        // Phase 2: Find start of the cycle
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        
        return slow;
    }
};

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def has_cycle(head: ListNode) -> bool:
    """
    Determines if there is a cycle in the linked list.
    
    Args:
        head: Head of the linked list
        
    Returns:
        True if there's a cycle, False otherwise
    """
    if not head or not head.next:
        return False
    
    slow = head
    fast = head
    
    while fast and fast.next:
        slow = slow.next       # Move one step
        fast = fast.next.next  # Move two steps
        
        if slow == fast:
            return True  # Cycle detected
    
    return False  # No cycle

def find_cycle_start(head: ListNode) -> ListNode:
    """
    Finds the node where the cycle begins.
    
    Args:
        head: Head of the linked list
        
    Returns:
        The node where the cycle begins, or None if no cycle
    """
    if not head or not head.next:
        return None
    
    # Phase 1: Detect if there's a cycle
    slow = fast = head
    has_cycle = False
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        return None
    
    # Phase 2: Find the start of the cycle
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # This is the cycle start node

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * Determines if there is a cycle in the linked list
 * @param {ListNode} head - Head of the linked list
 * @returns {boolean} True if there's a cycle, false otherwise
 */
function hasCycle(head) {
    if (!head || !head.next) {
        return false;
    }
    
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;       // Move one step
        fast = fast.next.next;  // Move two steps
        
        if (slow === fast) {
            return true;  // Cycle detected
        }
    }
    
    return false;  // No cycle
}

/**
 * Finds the node where the cycle begins
 * @param {ListNode} head - Head of the linked list
 * @returns {ListNode} The node where the cycle begins, or null if no cycle
 */
function detectCycle(head) {
    if (!head || !head.next) {
        return null;
    }
    
    // Phase 1: Detect cycle
    let slow = head;
    let fast = head;
    let hasCycle = false;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow === fast) {
            hasCycle = true;
            break;
        }
    }
    
    if (!hasCycle) {
        return null;
    }
    
    // Phase 2: Find cycle start
    slow = head;
    while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;  // This is the start of the cycle
}

Mathematical Insight

In Floyd's algorithm, when fast and slow pointers meet inside the cycle, the distance traveled by the fast pointer is twice the distance traveled by the slow pointer. This mathematical property enables finding the cycle start by resetting one pointer to the head and moving both pointers at the same speed.

Conclusion

The two-pointer technique is a powerful algorithmic pattern that provides elegant solutions to many common programming challenges. By managing two indices strategically, this approach enables efficient traversal and manipulation of data structures without requiring additional space.

Key Takeaways

Efficiency: Two-pointer algorithms typically achieve O(n) time complexity with O(1) space complexity, making them highly efficient for large datasets.
Versatility: The technique can be applied to various data structures including arrays, linked lists, and strings.
Implementation Patterns: The four main patterns—opposite direction, same direction, sliding window, and fast-slow pointers—cover a wide range of problem scenarios.
Preconditions: Many implementations require sorted data as a precondition for correctness.
Edge Cases: Careful handling of boundary conditions and edge cases is essential for robust implementations.

When to Use Two Pointers

When searching for pairs, triplets, or subarrays with specific properties
For in-place operations on arrays or linked lists
When you need to avoid using additional data structures for space efficiency
When the problem involves comparing elements from different positions

When to Avoid Two Pointers

When data isn't sorted and cannot be sorted without affecting the problem context
When random access to elements is required (not suitable for some linked list problems)
When global state needs to be maintained beyond local pointer positions

Always consider whether sorting the input (if not already sorted) would enable a more efficient two-pointer approach, even if it adds O(n log n) time complexity.

Further Resources

Books

"Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein
"Algorithms" by Robert Sedgewick and Kevin Wayne
"Cracking the Coding Interview" by Gayle Laakmann McDowell

Online Courses

MIT OpenCourseWare: Introduction to Algorithms
Stanford Algorithms Specialization on Coursera
Algorithmic Thinking courses on edX

Practice Problems

Two Sum (LeetCode #1)
Container With Most Water (LeetCode #11)
3Sum (LeetCode #15)
Remove Duplicates from Sorted Array (LeetCode #26)
Linked List Cycle (LeetCode #141)
Minimum Size Subarray Sum (LeetCode #209)

Binary Search
Merge Sort (uses two-pointer approach during merge)
Dutch National Flag Algorithm
Kadane's Algorithm (for maximum subarray)

Two Pointer

On this page