PATTERN 2 OF 22

Two Pointers

Use two pointers to traverse a sorted array or string from both ends (or at different speeds) to solve problems in O(n) time with O(1) space.

Time: O(n)

Space: O(1)

Learn & Reference

Understanding the Pattern

Two Pointers Pattern

Two pointers is one of the most versatile patterns in algorithm interviews. The idea is simple: instead of using nested loops (O(n²)), use two index variables that move through the data in a coordinated way to solve the problem in a single pass.

Core Concept

Place two pointers at strategic positions and move them based on a condition. The key insight is that pointer movement eliminates candidates — each step rules out an entire group of possibilities.

The 3 Two Pointer Archetypes

1. Opposite Ends (Converging)

Start one pointer at the beginning, one at the end. Move inward based on a condition. Works on sorted arrays and palindromes.

Why it works: In a sorted array, if the sum is too small, moving the left pointer right increases it. If too large, moving the right pointer left decreases it. Each step eliminates an entire row/column of the search space.

2. Same Direction (Fast & Slow)

Both pointers start at the beginning. The fast pointer explores ahead while the slow pointer marks a position. Used for removing duplicates in-place, partitioning, and cycle detection.

Why it works: The slow pointer marks "where to write next" while the fast pointer scans for the next valid element.

3. Two Sequences

One pointer per sequence. Advance whichever pointer points to the smaller element. Used for merging sorted arrays and intersection problems.

When Two Pointers Fails

When the array is not sorted (and sorting would lose required info like indices)
When you need to find ALL pairs, not just one (may need hash map instead)
When the problem requires non-contiguous elements
When O(1) space isn't possible (need auxiliary storage)

Common Mistakes

Forgetting to sort first: Two-pointer convergence only works on sorted data
Off-by-one on boundaries: Use < vs <= carefully with while (left < right)
Skipping duplicates incorrectly: When the problem says "unique triplets", skip duplicate values AFTER finding a match
Modifying array when indices matter: If you need original indices, use a hash map instead
Not handling empty or single-element arrays: Always check edge cases

When to Use

Array is sorted (or you can sort it)

Find a pair/triplet with a target sum

Check if string is a palindrome

Remove duplicates from sorted array in-place

Merge two sorted arrays

Container with most water / trapping rain water

Move zeroes to end

Problems asking for O(1) extra space

Reverse a string or array in-place

Squaring a sorted array

Template

1# --- Opposite Ends (Pair Sum) ---
2def pair_with_sum(nums, target):
3    """nums must be sorted"""
4    left, right = 0, len(nums) - 1
5    while left < right:
6        total = nums[left] + nums[right]
7        if total == target:
8            return [left, right]
9        elif total < target:
10            left += 1
11        else:
12            right -= 1
13    return []
14
15# --- Same Direction (Remove In-Place) ---
16def remove_element(nums, val):
17    """Remove all occurrences of val, return new length"""
18    slow = 0
19    for fast in range(len(nums)):
20        if nums[fast] != val:
21            nums[slow] = nums[fast]
22            slow += 1
23    return slow
24
25# --- Opposite Ends (Palindrome) ---
26def is_palindrome(s):
27    left, right = 0, len(s) - 1
28    while left < right:
29        if s[left] != s[right]:
30            return False
31        left += 1; right -= 1
32    return True

{ }

Syntax Reference

1# --- Opposite Ends ---
2left, right = 0, len(arr) - 1
3while left < right:
4    if condition(arr[left], arr[right]):
5        # found answer or process
6        left += 1   # or right -= 1
7    elif need_bigger:
8        left += 1
9    else:
10        right -= 1
11
12# --- Same Direction (fast/slow) ---
13slow = 0
14for fast in range(len(arr)):
15    if arr[fast] != val_to_skip:
16        arr[slow] = arr[fast]
17        slow += 1
18# slow = new length
19
20# --- Two Sequences ---
21i, j = 0, 0
22while i < len(a) and j < len(b):
23    if a[i] <= b[j]:
24        process(a[i]); i += 1
25    else:
26        process(b[j]); j += 1

📋

Common Recipes

1# --- Two Sum (sorted array) ---
2def two_sum_sorted(nums, target):
3    left, right = 0, len(nums) - 1
4    while left < right:
5        total = nums[left] + nums[right]
6        if total == target:
7            return [left, right]
8        elif total < target:
9            left += 1
10        else:
11            right -= 1
12    return []
13
14# --- Three Sum ---
15def three_sum(nums):
16    nums.sort()
17    result = []
18    for i in range(len(nums) - 2):
19        if i > 0 and nums[i] == nums[i-1]:
20            continue  # skip duplicates
21        left, right = i + 1, len(nums) - 1
22        while left < right:
23            total = nums[i] + nums[left] + nums[right]
24            if total == 0:
25                result.append([nums[i], nums[left], nums[right]])
26                while left < right and nums[left] == nums[left+1]:
27                    left += 1  # skip duplicates
28                while left < right and nums[right] == nums[right-1]:
29                    right -= 1
30                left += 1; right -= 1
31            elif total < 0:
32                left += 1
33            else:
34                right -= 1
35    return result
36
37# --- Is Palindrome ---
38def is_palindrome(s):
39    left, right = 0, len(s) - 1
40    while left < right:
41        if s[left] != s[right]:
42            return False
43        left += 1; right -= 1
44    return True
45
46# --- Remove Duplicates In-Place ---
47def remove_duplicates(nums):
48    if not nums:
49        return 0
50    slow = 0
51    for fast in range(1, len(nums)):
52        if nums[fast] != nums[slow]:
53            slow += 1
54            nums[slow] = nums[fast]
55    return slow + 1
56
57# --- Container With Most Water ---
58def max_area(height):
59    left, right = 0, len(height) - 1
60    best = 0
61    while left < right:
62        area = min(height[left], height[right]) * (right - left)
63        best = max(best, area)
64        if height[left] < height[right]:
65            left += 1
66        else:
67            right -= 1
68    return best

O(n)

Complexity

Operation	Time	Space
Pair sum (sorted)	O(n)	O(1)
Three sum	O(n²)	O(1)
Remove duplicates	O(n)	O(1)
Merge sorted	O(n+m)	O(n+m)
Palindrome check	O(n)	O(1)

Watch Out

✗When the array is not sorted (and sorting would lose required info like indices)
✗When you need to find ALL pairs, not just one (may need hash map instead)
✗When the problem requires non-contiguous elements
✗When O(1) space isn't possible (need auxiliary storage)
✗Forgetting to sort first: Two-pointer convergence only works on sorted data
✗Off-by-one on boundaries: Use < vs <= carefully with while (left < right)
✗Skipping duplicates incorrectly: When the problem says "unique triplets", skip duplicate values AFTER finding a match
✗Modifying array when indices matter: If you need original indices, use a hash map instead
✗Not handling empty or single-element arrays: Always check edge cases

PRACTICE PROBLEMS

Hash Maps

Sliding Window