Overview & Concept

The Two Pointers Technique uses two converging or co-directional index references to traverse a sequence simultaneously. In sorted array target sum problems, starting one pointer at the beginning and the other at the end achieves optimal O(n) linear search without hash table memory.

How It Works

Opposing Convergence: Left pointer starts at index 0 (smallest); right pointer starts at index n-1 (largest).

Current Sum Evaluation: Calculates sum = arr[left] + arr[right].

Directional Shift: If sum < target, left++ increases the sum; if sum > target, right-- decreases the sum.

Linear Convergence: Pointers move monotonically inward, inspecting each element at most once.

Step-by-Step Execution

1. Initialize PointersSet left = 0 and right = n - 1 on sorted array.

2. Compute SumEvaluate sum = arr[left] + arr[right].

3. Compare with TargetIf sum == target, return [left, right]. If sum < target, left++. If sum > target, right--.

4. TerminateContinue while left < right. If left >= right, no such pair exists.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(1)	O(n)	O(n)	O(1)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure twoPointersSearch(A, target):
  left = 0, right = length(A) - 1
  while left < right:
    sum = A[left] + A[right]
    if sum == target: return [left, right]
    else if sum < target: left = left + 1
    else: right = right - 1
  return [-1, -1]

Algorithmic Invariants

Search Boundary Invariant: If a valid pair exists, its indices must reside within [left, right].

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•O(n) linear time without allocating auxiliary memory: runs in strictly O(1) extra space.
•Exceptional cache locality and minimal branch misprediction.

Trade-offs & Limitations

•Requires array to be pre-sorted: if unsorted, sorting costs O(n log n).

Real-World Applications

Sorted Two-Sum / Three-Sum

Finding numbers that sum to a zero or target balance in financial ledgers.

Container with Most Water

Computing maximum geometric area enclosed between vertical coordinate lines.

Decision Guide: When to Use

Ideal Scenarios

✓When searching pairs in sorted data where auxiliary hash memory is restricted.

Consider Alternatives When

✕When data is unsorted and queried only once (hash map offers O(n) without sorting).

Compare trade-offs and complexity across complementary tools in AlgoViz.

Binary Search Sliding Window Search