Two Pointer Algorithm
The two-pointer algorithm is a powerful and elegant strategy often used in solving array, string, and linked list problems. It involves using two indices (or “pointers”) that move through the data structure—either toward each other, away from each other, or in the same direction—based on specific conditions.
This method is especially effective in reducing the time complexity of problems that would otherwise require nested loops (\(O(n^2)\)) to linear or linearithmic time (\(O(n)\) or \(O(n\ log\ n)\)). Instead of checking all combinations, the two-pointer technique allows you to traverse the data structure in a more intelligent, goal-oriented way.
Key Characteristics:
- Typically requires the data structure (like an array) to be sorted.
- Often involves in-place operations.
- Helps solve problems with minimal space overhead.
🛠️ When to Use the Two-Pointer Technique
The two-pointer method is ideal in scenarios where you’re working with a linear data structure and need to optimize performance. Here are common use cases where it shines:
✅ 1. Finding Pairs or Triplets in a Sorted Array
Example: Find two numbers that sum to a target. Why: Allows scanning from both ends, avoiding nested loops.
✅ 2. Removing or Skipping Duplicates
Example: Remove duplicates in-place from a sorted array. Why: One pointer tracks unique values, the other scans ahead.
✅ 3. Reversing or Swapping Elements In-Place
Example: Reverse a string or array. Why: Use one pointer at the start and one at the end to swap efficiently.
✅ 4. Partitioning or Rearranging Elements
Example: Move all zeroes to the end or sort colors (Dutch flag problem). Why: Pointers can guide element swaps without extra space.
✅ 5. Palindrome Checking
Example: Check if a string is a palindrome. Why: Compare characters from both ends inward.
✅ 6. Merging or Comparing Two Sorted Lists/Arrays
Example: Merge two sorted arrays. Why: Move pointers based on comparison to maintain order.
✅ 7. Cycle Detection or Sliding Window Variants
Example: Detect cycles in linked lists (fast/slow pointer). Why: Use different speeds or ranges to find patterns or windows.
Vaild Palindrome
Reverse String
📝 Suggested Practice Problems
Easy
Medium
Hard