logo
Lembog Tools
logo
šŸ“š
0
Lvl 1
0
DSA Pattern #1

šŸ‘†šŸ‘†Two Pointer Pattern

Learn how to use two pointers to solve array problems in linear time, turning O(nĀ²) brute force into elegant O(n) solutions.

šŸ“–Introduction

Imagine you're at a library with books arranged by height on a shelf. You need to find two books whose combined height equals exactly 16 inches.

The Two Pointer pattern is one of the most elegant techniques in algorithm design. Instead of comparing every possible pair of elements (which takes O(nĀ²) time), we use two pointers that move toward each other, solving the problem in just one pass through the array.

When to use Two Pointers?

  • āœ“ The array is sorted (or can be sorted)
  • āœ“ You need to find pairs, triplets, or subarrays
  • āœ“ You want to compare elements from different ends
  • āœ“ You need to partition or rearrange elements in-place

šŸ¤”The Problem

Classic Problem: Two Sum (Sorted Array)

Given a sorted array of integers and a target sum, find two numbers that add up to the target.

Input: [1, 3, 5, 7, 9, 11, 13, 15]Target: 16

Brute Force: Check every pair ā†’ O(nĀ²) time
Two Pointer: Start from both ends ā†’ O(n) time

šŸ’”The Insight

Because the array is sorted, we can make intelligent decisions:

Sum too small? šŸ”¼

Move the left pointer right to pick a larger number.

Sum too large? šŸ”½

Move the right pointer left to pick a smaller number.

This way, we eliminate possibilities with each step, guaranteeing we find the answer (if it exists) in at most n steps!

šŸ‘€See It In Action

Watch how two pointers move through the array to find the target sum of 14.

Target Sum:14

Ready to start

Step 1 of 0
 1function findPairWithSum(arr, target) {
 2  let left = 0, right = arr.length - 1;
 3  
 4  while (left < right) {
 5    const sum = arr[left] + arr[right];
 6    if (sum === target) return [left, right];
 7    
 8    if (sum < target) left++;
 9    else right--;
10  }
11  return null;
12}

šŸŽļøComplexity Race

See the dramatic difference between brute force O(nĀ²) and two pointer O(n).

āš” Complexity Race

Watch how Two Pointer O(n) beats Brute Force O(nĀ²)

šŸ¢

Brute Force

O(nĀ²)

0

/ 400 ops

for (i = 0; i < n; i++)
for (j = i+1; j < n; j++)
šŸš€

Two Pointer

O(n)

0

/ 20 ops

while (left < right)
// Single pass through array
Array size: n = 20 | Brute Force: nĀ² = 400 | Two Pointer: n = 20

šŸŽ®Practice Challenges

Now it's your turn! Control the pointers to find the target sum.

Find the Pair

easy

Find two numbers that add up to the target

0:00
0/4
Find pair that sums to:12
L
1
0
2
1
4
2
6
3
8
4
R
10
5
1 + 10 = 11

Left Pointer

Right Pointer

Larger Array

medium

Same concept, bigger challenge

0:00
0/4
Find pair that sums to:24
L
1
0
3
1
5
2
7
3
9
4
11
5
13
6
15
7
17
8
R
19
9
1 + 19 = 20

Left Pointer

Right Pointer

Edge Cases

hard

Handle the tricky spots

0:00
0/4
Find pair that sums to:18
L
2
0
4
1
6
2
8
3
10
4
12
5
14
6
R
16
7
2 + 16 = 18āœ“ Target found!

Left Pointer

Right Pointer

āœ…Summary

Key Takeaways

  • Two pointers work best on sorted arrays
  • Move pointers based on comparison with target
  • Time complexity: O(n) vs O(nĀ²) brute force
  • Space complexity: O(1) - no extra space needed

Common Variations

  • ā€¢ Three Sum (3 pointers)
  • ā€¢ Container With Most Water
  • ā€¢ Remove Duplicates In-Place
  • ā€¢ Palindrome Check
  • ā€¢ Dutch National Flag Problem

šŸŽ‰ Congratulations!

You've completed the Two Pointer Pattern lesson!

Back to Learn Hub