👉 Two Pointer Technique

Use two pointers to traverse data structures efficiently. Master collision, fast-slow, and sliding pointer patterns.

Overview

ℹ️

What is Two Pointer?

The two pointer technique uses two pointers to iterate through data, often in opposite directions or at different speeds. It reduces time complexity by avoiding nested loops. Common patterns: collision (left/right), fast-slow, and parallel iteration.

Key Two Pointer Algorithms

Two Sum (Sorted)

Find two numbers in sorted array that sum to target

Time: O(n)Space: O(1)

Remove Duplicates

Remove duplicates from sorted array in-place

Time: O(n)Space: O(1)

Container With Most Water

Find max water between two lines

Time: O(n)Space: O(1)

3Sum

Find all triplets summing to zero

Time: O(n²)Space: O(1)

Valid Palindrome

Check if string is palindrome with two pointers

Time: O(n)Space: O(1)

Interactive Visualizer

Pointer Visualization

👉

Two Sum (Sorted) Visualizer

Watch how pointers move across the array, making decisions based on element values.

Deep Dive: Two Sum (Sorted)

Time Complexity

Time: O(n)

Space Complexity

Space: O(1)

Pattern

Collision

💡

Pointer Strategy

Start with left=0, right=last. If sum < target, move left up. If sum > target, move right down. The sorted property guarantees correctness.

python

def twoSumSorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        curr = arr[left] + arr[right]
        if curr == target:
            return [left, right]
        elif curr < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

1

Position Pointers

Decide initial positions: both ends, same start, or offset.

2

Compare Values

Evaluate elements at pointer positions against target or each other.

3

Move Pointers

Advance one or both pointers based on comparison result.

4

Repeat

Continue until pointers meet, cross, or reach end.

Real-World Applications

Array Partitioning

QuickSort partitioning, Dutch national flag problem

String Processing

Palindrome checking, reverse words in place

Data Validation

Validating sequences, detecting cycles in linked lists

Memory Management

Compacting arrays, defragmentation algorithms

Search Optimization

Two pointers reduce O(n²) to O(n) for pair problems

Linked List

Detect cycle (Floyd's), find middle, remove nth from end

Interview Questions

What are the three common two-pointer patterns?

1) Collision: pointers start at ends and move inward (Two Sum, Palindrome), 2) Fast-Slow: one pointer moves faster (Remove Duplicates, Cycle Detection), 3) Parallel: both start at same end at different speeds.

When would you use two pointers vs hash map?

Two pointers uses O(1) space, ideal for sorted arrays. Hash map uses O(n) space but works on unsorted data. If array is sorted or sortable, prefer two pointers.

How do you adapt two-pointer for 3Sum?

Sort array, iterate with one pointer as 'anchor', then use two-pointer pair search on the remaining subarray. Total: O(n²) time, O(1) extra space.

Knowledge Check

1. When is two pointer technique most effective?

2. Time complexity of two-pointer pair problems?

3. What type of pointer is used in Remove Duplicates?

4. How does Container With Most Water decide which pointer moves?

5. What is the time complexity of 3Sum?

What's Next?

Advanced Concepts

Build on these skills: