Faangprep Logo
LoginRegister
Two Pointers
Easy

Introduction to Two Pointers

A space-efficient technique to traverse arrays and strings using two reference points significantly reducing time complexity.
10 min
Time: O(n)
Space: O(1)
Solve on LeetCode
Examples
Input:nums = [2,7,11,15], target = 9
Output:[0,1]
Explain:

Because nums[0] + nums[1] == 9, we return [0, 1].

Input:nums = [3,2,4], target = 6
Output:[1,2]
What is the Two Pointer Technique?

The Two Pointer technique is a fundamental strategy where you use two separate reference points (pointers) to traverse a data structure, usually an array or a string.

Instead of using a single loop to scan elements one by one (or nested loops to check every pair), we use two pointers to process information from different positions simultaneously. By moving these pointers based on specific conditions, we can solve problems much faster. This simple trick often turns a slow O(n^2) brute-force solution into an efficient O(n) linear solution.

The Motivation: Two Sum (Sorted)

Now, let's look at a classic problem to see why this technique is so useful.

"Given a sorted array of integers, find two numbers that sum up to a specific target."

Example:

  • Input: nums = [1, 3, 4, 6, 8, 10, 13]
  • Target: 13
  • Goal: Find two numbers that add to 13. (Answer: 3 + 10)
Attempt 1: Brute Force (Why it fails)

Your first instinct might be to check every single pair.

"Okay, let's try 1+3, 1+4, 1+6... then 3+4, 3+6..."

While this gives the correct answer, it is extremely inefficient.

  • Time Complexity: O(n^2). For an array of 10,000 items, that's 100 million checks!
  • The Issue: You are doing repetitive work and ignoring the most important clue: The array is sorted.
Visualizing the Brute Force Approach
Step 1 / 5
i
1
0
j
3
1
4
2
6
3
8
4
10
5
13
6

Check pair (1, 3). Sum = 4. (Too small). Move inner loop j.

1x
When should I use Two Pointers?

Pattern Recognition Triggers:

In an interview, consider this pattern immediately if you see:

  1. Sorted Input: The problem mentions a "sorted array" or implies you can sort it.
  2. Pair/Triplet Search: You need to find sets of elements (pairs, triplets).
  3. Minimize/Maximize: You need to find a pair with min/max distance or sum.
  4. Opposite Ends: The logic suggests checking extremes (smallest vs largest).
The Intuition: Process of Elimination

Let's work smarter, not harder.
Instead of blindly checking pairs, let's use the sorted order to eliminate wrong answers.

Key Insight:
If the sum of our current pair is Too Big, keeping the larger number is useless. It will always trigger a "Too Big" result with any other number. So, we can permanently discard (eliminate) the larger number.

Interactive Walkthrough
Step 1 / 6
L
1
0
3
1
4
2
6
3
8
4
10
5
R
13
6

Start at the ends (1 and 13). Sum = 14. Target = 13.

1x
Dry Run Table
Step Left Pointer (val) Right Pointer (val) Sum Action
1 Index 0 (1) Index 6 (13) 14 > 13. Too big. Move Right --
2 Index 0 (1) Index 5 (10) 11 < 13. Too small. Move Left ++
3 Index 1 (3) Index 5 (10) 13 == 13. Found it! Return True
The Solution Template
1def two_sum(nums, target):
2    left = 0
3    right = len(nums) - 1
4

5    while left < right:
6        current_sum = nums[left] + nums[right]
7

8        if current_sum == target:
9            return True
10        elif current_sum < target:
11            left += 1
12        else:
13            right -= 1
14            
15    return False
Edge Cases & Common Mistakes

Edge Case Checklist:

  • Empty Array: Return false/empty immediately.
  • One Element: Loop condition left < right handles this naturally (won't run).
  • No Solution: Ensure you handle the return value after the loop finishes.

Common Mistakes:

  • Not Sorting: This pattern ONLY works on sorted arrays. If unsorted, sort first (O(n log n)).
  • Wrong Loop Condition: Use left < right for pairs. Use left <= right only if a single element can be the answer.
Time & Space Analysis
  • Time Complexity: O(n). We touch each element at most most once.
  • Space Complexity: O(1). We use no extra memory.
Summary

Recap:

  • The Trick: Use sorted order to eliminate pairs.
  • Movement: Sum too small → Increase left. Sum too big → Decrease right.
  • Efficiency: We turned a slow O(n^2) search into a blazing fast O(n) scan.
Next Lesson
Two Sum II - Input Array Is Sorted