Two Pointers Technique
High ImportanceCoordinate two indices through a sequence to eliminate redundant candidate combinations in O(1) per step, dropping O(N²) brute force to O(N).
When to Use Two Pointers:
Key problem characteristics and signals indicating that this technique is the optimal choice.
Sorted array or string pair search matching a target sum, difference, or product.
In-place array element compaction, deduplication, or partitioning without extra memory.
Symmetrical boundary verification such as palindrome validation and string reversal.
Monotonic area/container optimization where moving the bottleneck pointer strictly explores better candidates.
Prerequisite Rule: For pair-sum and range search problems, the array must be sorted (or sortable in O(N log N)). If original unsorted indices must be returned and sorting is prohibited, a Hash Map O(N) space approach is standard.
Example Problem — Sum of Pair Equal to Target
The benchmark interview problem demonstrating the transition from quadratic brute force to linear optimality.
Problem Statement
Given a sorted array of integers arr[] and an integer target, determine whether there exists any pair of elements (arr[i], arr[j]) such that their sum equals the target. If such a pair exists, return True (or the pair / indices); otherwise, return False.
arr = [1, 2, 4, 6, 8, 11], target = 10
True (Pair: 2 + 8 = 10 at indices [1, 4])
Explanation: Elements 2 (index 1) and 8 (index 4) sum up to 2 + 8 = 10, which matches target.
Naive Method — O(n²) Time and O(1) Space
The baseline brute force approach recalculating candidates through nested loops.
The brute force approach generates all possible pairs of elements from the array using two nested loops and checks if the sum of any pair equals the target.
def pair_sum_naive(arr: list[int], target: int) -> bool: n = len(arr) # Check every possible pair (i, j) where i < j for i in range(n): for j in range(i + 1, n): if arr[i] + arr[j] == target: return True # Found pair (arr[i], arr[j]) return False # No such pair existsWhy Naive Fails in Production & Interviews
For an array with n = 10⁵ elements, n(n - 1) / 2 comparisons would require ~5 × 10⁹ operations. In competitive programming and tech interviews, this causes a Time Limit Exceeded (TLE) error. The fundamental flaw of the naive method is that it completely ignores the sorted order of the array, re-evaluating hopeless combinations.
Two-Pointer Technique — O(n) Time and O(1) Space
The optimal strategy leveraging two pointers mechanics to achieve optimal time complexity.
By maintaining two pointers at opposite ends of the sorted array, we can determine whether to increase or decrease the sum in O(1) time at each step.
Initialize Pointers: Set left = 0 (pointing to the minimum element) and right = n - 1 (pointing to the maximum element).
Calculate Current Sum: At each iteration, compute current_sum = arr[left] + arr[right].
Evaluate Match (current_sum == target): We found the target! Return True (or return the pair indices [left, right]).
Sum is Too Small (current_sum < target): Because the array is sorted, pairing arr[left] with any element smaller than arr[right] will produce an even smaller sum. Thus arr[left] cannot be part of any valid pair with the remaining elements. We advance left forward (left++).
Sum is Too Large (current_sum > target): Because the array is sorted, pairing arr[right] with any element larger than arr[left] will produce an even larger sum. Thus arr[right] cannot be part of any valid pair with the remaining elements. We advance right backward (right--).
Interactive Trace
Interactive Trace: Two Sum II (Converging Two Pointers)
Interactive Trace: Two Sum II (Converging Two Pointers)
arr = [1, 2, 4, 6, 8, 11], target = 10
Indices [1, 4] (Values: 2 + 8 = 10)
State Mutation Inspector
Decision & Invariant Action
Since 1 + 11 = 12 > 10 and the array is sorted, pairing 11 with any number > 1 will also exceed 10. We can safely eliminate 11 forever.
Two Pointers Algorithm Code
Complete runnable solution in Python, C++, Java, and JavaScript.
def two_pointers_converging(arr: list[int], target: int) -> list[int]: """ Two-Pointer Technique: Pair Sum Equal to Target Time Complexity: O(n) | Space Complexity: O(1) """ left, right = 0, len(arr) - 1 while left < right: current_sum = arr[left] + arr[right] if current_sum == target: return [left, right] # Target pair found! elif current_sum < target: left += 1 # Need a larger sum -> move left inward else: right -= 1 # Need a smaller sum -> move right inward return [-1, -1] # No valid pair existsHow does this work?
Invariant Proof & Why It Is Guaranteed to Never Miss a Valid Pair
The power of Two Pointers comes from sorted monotonicity: each comparison permanently discards an entire candidate element in O(1) time without risking false negatives.
1. Sorted Monotonicity Invariant
The array satisfies arr[0] <= arr[1] <= ... <= arr[n-1]. Consequently, fixing any index i and increasing j strictly increases arr[i] + arr[j]. Conversely, decreasing j strictly decreases the sum.
2. Why is discarding arr[right] safe when sum > target?
If arr[left] + arr[right] > target, then since arr[left] is the smallest active element in our candidate window [left ... right], any other element arr[k] (where k >= left) is at least as large as arr[left]. Therefore, arr[k] + arr[right] >= arr[left] + arr[right] > target for all k in [left, right - 1]. This guarantees arr[right] cannot pair with ANY remaining candidate to form target. Discarding right (right--) is 100% mathematically safe.
3. Why is discarding arr[left] safe when sum < target?
If arr[left] + arr[right] < target, then since arr[right] is the largest active element in our window, any other element arr[k] (where k <= right) satisfies arr[left] + arr[k] <= arr[left] + arr[right] < target. Therefore, arr[left] cannot pair with ANY remaining candidate to reach target. Discarding left (left++) eliminates no valid solutions.
4. The Convergence Guarantee
Suppose an optimal solution exists at (i*, j*). The pointers begin at 0 <= i* and n - 1 >= j*. Whichever pointer reaches its boundary coordinate (i* or j*) first will freeze or wait because every subsequent sum comparison will strictly push the other pointer toward its matching coordinate. Neither pointer can ever cross over the true solution!
Core Pattern Variations & Blueprints
Explore the 3 structural variations that power all two pointers interview problems. Click each variation to expand its blueprint, interactive dry run, and implementation.
Left pointer starts at 0, Right pointer starts at N-1. Pointers move inward toward each other based on sorted monotonicity or symmetry.
The Algorithmic Invariant
If arr[left] + arr[right] > target, then pairing arr[right] with ANY element after left will also exceed target. Thus arr[right] can be permanently eliminated in O(1).
Pointer Traversal Flow
[ 1 ] [ 2 ] [ 4 ] [ 6 ] [ 8 ] [ 11 ]
↑ ↑
left ──► ◄── right
(Starts at 0) (Starts at N-1)Worked Example: Two Sum II — Input Array Is Sorted (Target = 10)
arr = [1, 2, 4, 6, 8, 11], target = 10Step 1: left=0 (val: 1), right=5 (val: 11). Sum = 1 + 11 = 12 > 10. Pairing 11 with any number > 1 would be even larger. Safely discard 11 -> right--.
Step 2: left=0 (val: 1), right=4 (val: 8). Sum = 1 + 8 = 9 < 10. Pairing 1 with any number <= 8 cannot reach 10. Safely discard 1 -> left++.
Step 3: left=1 (val: 2), right=4 (val: 8). Sum = 2 + 8 = 10 == 10. Match found! Return 1-based indices [2, 5] (or 0-based [1, 4]).
Interactive Dry Run Simulator
Converging Invariant Trace: Two Sum II
arr = [1, 2, 4, 6, 8, 11], target = 10
Indices [1, 4] (2 + 8 = 10)
State Mutation Inspector
Decision & Invariant Action
1 + 11 = 12 > 10. Discard 11 permanently because 11 with any number > 1 will also exceed 10.
Production-Grade Implementation
def two_pointers_converging(arr: list[int], target: int) -> list[int]: """ Standard Converging Two Pointers Template Time Complexity: O(N) | Space Complexity: O(1) """ left, right = 0, len(arr) - 1 while left < right: current_sum = arr[left] + arr[right] if current_sum == target: return [left, right] elif current_sum < target: left += 1 # Need a larger sum -> move left inward else: right -= 1 # Need a smaller sum -> move right inward return [-1, -1] # No pair foundLandmine to Avoid: Off-by-one loop boundary: using `while left <= right` instead of `while left < right` for pair search, which accidentally pairs an element with itself.
Curated Practice Ladder
Master this pattern progressively through verified interview questions.
Create a free account to track progress and unlock your free practice set.
Premium also includes the full problem library, detailed solutions, hints, and advanced revision tools.
Already have an account? Log in
“Master the invariants,
and the solution
writes itself.”
