Two Pointers

Two Pointers is a technique that uses two indices to traverse data, eliminating the need for nested loops.

The Race Track Analogy: Imagine two runners on a track:

• •Opposite direction: Start at opposite ends, run toward each other
• •Same direction: Start together, one runs faster than the other

Visual Representation:

Why Two Pointers?

• •Reduces O(n²) brute force to O(n)
• •Uses O(1) extra space
• •Works naturally with sorted arrays
• •Elegant solutions to complex problems

The Core Insight: Instead of checking ALL pairs (n² pairs), use pointers strategically to SKIP unnecessary comparisons based on problem constraints.

Two Pointers is one of the most common patterns in coding interviews.

Frequency:

• •Appears in 20-30% of FAANG coding rounds
• •Foundation for many other patterns (Sliding Window, Fast/Slow)
• •Often combined with sorting

What Interviewers Test:

1. •Optimization Thinking - Can you improve brute force?
2. •Sorted Array Skills - Do you leverage sorted order?
3. •In-Place Modifications - Can you avoid extra space?
4. •Edge Case Handling - Duplicates, empty arrays, boundaries

The Two Main Variants:

Key Insight: Sorting often ENABLES two pointers. If brute force is O(n²), consider if O(n log n) sort + O(n) two pointers is better.

Two pointers starting at opposite ends, moving toward center.

When to Use:

• •Finding pairs with target sum in SORTED array
• •Palindrome checking
• •Container/area problems
• •Reversing in-place

The Template:

Why It Works on Sorted Arrays:

Each move eliminates multiple pairs at once → O(n)!

The classic opposite-direction problem. Find two numbers that sum to target.

Visual Trace: arr = [2, 7, 11, 15], target = 9

Proof of Correctness: We never skip a valid pair because:

• •Moving left++ only when sum < target (keeping right won't help)
• •Moving right-- only when sum > target (keeping left won't help)

Find two vertical lines that form a container holding the most water.

Key Formula: Area = min(height[left], height[right]) × width

The Greedy Insight: Start with the WIDEST container (left=0, right=n-1). As we shrink width, we need TALLER lines to compensate. So always move the SHORTER line inward.

Why Move the Shorter Line?

Calculate how much water can be trapped after raining. A harder variant!

Key Insight: Water at position i = min(maxLeft, maxRight) - height[i]

Two Pointer Approach: Track maxLeft and maxRight as we go. Process the side with smaller max.

Why Process Smaller Max Side?

Both pointers move in the same direction at different speeds or conditions.

When to Use:

• •Removing elements in-place
• •Removing duplicates
• •Partitioning arrays
• •Finding cycle (linked lists)

The Template:

Visual Concept:

Key Insight: Slow marks the "frontier" of valid elements. Fast explores ahead.

Remove duplicates IN-PLACE from sorted array. Return new length.

The Logic:

• •slow: position of last unique element
• •fast: scans for next unique element
• •When fast finds new value, copy to slow+1

Visual Trace: [1, 1, 2, 2, 3]

Remove all occurrences of a value IN-PLACE. Return new length.

Simpler than Remove Duplicates:

• •Just skip elements equal to val
• •Copy everything else to slow position

Example: nums = [3, 2, 2, 3], val = 3

Move all zeroes to end while maintaining relative order of non-zeroes.

Two Approaches:

Approach 1: Copy then fill

Approach 2: Swap

Example: [0, 1, 0, 3, 12]

Find ALL unique triplets that sum to zero. Combines outer loop with two pointers.

Algorithm:

1. •Sort the array
2. •Fix first element with outer loop (i)
3. •Use two pointers for remaining pair (left, right)
4. •Skip duplicates at ALL levels to avoid duplicate triplets

Why Sort?

• •Enables two pointers for inner pair
• •Makes duplicate skipping easy (identical elements are adjacent)

Duplicate Handling (CRITICAL):

Find all unique quadruplets that sum to target. Same pattern, one more loop!

Pattern Extension:

4Sum Algorithm:

1. •Sort the array
2. •First loop fixes first element (i)
3. •Second loop fixes second element (j)
4. •Two pointers find remaining pair
5. •Skip duplicates at ALL levels

Check if string is palindrome (alphanumeric only, ignore case).

Two Pointer Approach:

1. •Start from both ends
2. •Skip non-alphanumeric characters
3. •Compare characters (case-insensitive)
4. •If mismatch found → not palindrome
5. •If pointers meet → palindrome

Example: "A man, a plan, a canal: Panama"

Can string become palindrome by deleting at most ONE character?

Algorithm:

1. •Use two pointers from both ends
2. •If mismatch found, try deleting left OR deleting right
3. •Check if either resulting substring is palindrome

Example: "abca"

Sort array with only 0s, 1s, and 2s using THREE pointers.

The Three Regions:

Rules:

• •nums[mid] == 0: swap with low, advance both
• •nums[mid] == 1: just advance mid
• •nums[mid] == 2: swap with high, only decrement high (don't advance mid!)

Why Not Advance Mid After Swapping with High? The swapped value from high is UNKNOWN - we need to examine it!

Given sorted array (may have negatives), return squares in sorted order.

Key Insight: Largest squares are at the ENDS (most negative or most positive).

Algorithm: Use opposite direction pointers, build result from END to START.

Example: [-4, -1, 0, 3, 10]

Master these to avoid interview pitfalls.

1. Empty Array

2. Single Element

3. All Same Elements

4. All Zeros / All Target Value

5. Already Sorted Result

6. Negative Numbers

7. Integer Overflow

8. Loop Condition

Quick reference for choosing the right approach:

Decision Tree:

Time Complexity:

• •Single pass two pointers: O(n)
• •With sorting: O(n log n) + O(n) = O(n log n)
• •Nested with two pointers (3Sum): O(n²)
• •Double nested (4Sum): O(n³)

Space Complexity:

• •In-place modifications: O(1)
• •If sorting creates copy: O(n) or O(log n) for sort

Why Two Pointers Achieves O(n):

Comparison to Brute Force:

Copy-paste ready templates.

Template 1: Opposite Direction

Template 2: Same Direction (Filter)

Template 3: Same Direction (Remove Duplicates)

Template 4: Dutch National Flag

Template 5: 3Sum Pattern