When should I use Two Pointers?

Finding pairs in a sorted array. Reversing an array (swapping elements at L and R). Partitioning (like in QuickSort).

Is Two Pointers asked in FAANG interviews?

Yes, Two Pointers is commonly tested in FAANG and top tech company interviews.

Two Pointers

Q: What is the time complexity of Two Pointers?

Best: varies, Average: O(N), Worst: varies. Space: varies.

Visualize the Two Pointers technique for finding a pair with a specific sum in a sorted array.

Target Sum

Ready to find pair.

2

3

5

8

11

14

18

23

Intuition

Instead of using nested loops to check every pair (O(n²)), we can use two pointers starting at the ends of a sorted array to find a pair with a target sum in O(n) time.

Concept

Sorted Array: Essential for this technique.
Left Pointer (L): Starts at 0.
Right Pointer (R): Starts at n-1.
Logic: If sum < target, we need a larger sum, so move L right. If sum > target, we need a smaller sum, so move R left.

How it Works

Algorithm:

Initialize L = 0, R = n - 1.
While L < R:
Calculate sum = arr[L] + arr[R].
If sum == target, return pair.
If sum < target, increment L.
If sum > target, decrement R.

Step-by-Step Breakdown

Watch the visualization:

See how the pointers move towards each other.
Notice that we never check the same pair twice or backtrack.

When to Use

Finding pairs in a sorted array.
Reversing an array (swapping elements at L and R).
Partitioning (like in QuickSort).

When NOT to Use

Unsorted arrays (unless you sort them first).
When you need to find indices in the original unsorted array (indices change after sorting).

How to Identify

"Find a pair...", "Sorted array", "In-place reversal".

Sample Problems

Two Sum II - Input Array Is Sorted

Find two numbers that add up to a specific target number.

Valid Palindrome

Check if a string is a palindrome (using two pointers).

Array Operations

Sliding Window

Frequently Asked Questions

What is Two Pointers?