logo
Lembog Tools
📚
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?

  • ✓Sorted array (or can be sorted)
  • ✓Need to find pairs/triplets
  • ✓Compare elements from both ends
  • ✓Partition array 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 | O(1) Space

Two Pointer Option

Start from both ends

O(N) Time | O(1) Space

The Insight

Because the array is sorted, we can make highly intelligent decisions without checking all pairs:

🔼Sum is Too Small

Move the left pointer right to increase the value of the next sum.

🔽Sum is Too Large

Move the right pointer left to decrease the value of the next sum.

💡 The Magic: With every step, we discard choices that can never possibly lead to our target sum. This guarantees we either find the answer or determine that none exists in a maximum of n operations!

See It In Action

Watch how two pointers move through the array to find the target sum of 14 in real-time.

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 astronomical difference in performance between the O(N²) brute-force solution and the O(N) Two Pointer optimization as the data size grows.

⚡ 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! Put your knowledge to the test. Control the left and right pointers directly to find the target sum in each challenge.

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 inward based on sum comparison with target
  • Drastically reduces time complexity from O(N²) to O(N)
  • Excellent space complexity: O(1) auxiliary space

Common Variations

  • Three Sum
  • Most Water Container
  • Remove Duplicates
  • Palindrome Check
  • Dutch National Flag (3-Way Partition)

🎉 Congratulations!

You've completed the Two Pointer Pattern lesson! You are ready to tackle linear-time array searching.

Back to Learn Hub