The Two Pointers technique is an algorithmic pattern, primarily used with sorted arrays or linked lists. It involves using two pointers (variables that usually store array indices or node references) that traverse the data structure from different ends or at different speeds.

Core Idea:

The Two Pointers technique is an algorithmic pattern, primarily used with sorted arrays or linked lists. It involves using two pointers (variables that usually store array indices or node references) that traverse the data structure from different ends or at different speeds.

Common Scenarios & How it Works:

  1. Opposite Ends (e.g., finding a pair with a specific sum in a sorted array):
    • One pointer (left) starts at the beginning, and the other (right) starts at the end.
    • You calculate a value based on the elements at these pointers (e.g., sum = array[left] + array[right]).
    • If the sum is less than the target, you move the left pointer one step to the right (to increase the sum).
    • If the sum is greater than the target, you move the right pointer one step to the left (to decrease the sum).
    • If the sum equals the target, you’ve found your pair.
    • The process continues until the pointers meet or cross. This approach typically achieves O(n) time complexity.
  2. Slow and Fast Pointers (e.g., detecting cycles in a linked list, finding the middle element):
    • One pointer (slow) moves one step at a time.
    • Another pointer (fast) moves two steps (or more) at a time.
    • The relative positions or meeting point of these pointers help solve the problem.
  3. Sliding Window (e.g., finding the minimum/maximum sum subarray of a fixed size):
    • Two pointers define a “window” (a subarray or substring).
    • Both pointers usually move in the same direction. The end pointer expands the window, and the start pointer shrinks it from the left.
    • This helps in efficiently processing contiguous parts of the data.

Advantages:

  • Efficiency: Often reduces time complexity from O(n^2) or O(n^3) (brute-force) to O(n).
  • Space Complexity: Usually O(1) as it modifies the array/list in place or uses a fixed number of extra variables.

When to Use:

  • Problems involving sorted arrays where you need to find pairs or subsequences with certain properties (e.g., sum, difference).
  • Problems on linked lists like cycle detection, finding the middle, or reversing parts of the list.
  • String manipulation problems.
  • Problems requiring finding a contiguous subarray/substring that satisfies some condition.

Example LeetCode Problems:

  1. (#11) Container With Most Water
  2. (#15) 3Sum
  3. (#167) Two Sum II - Input Array Is Sorted