Two Pointers Introduction
What is Two Pointers?
Two pointers is a technique where you use two variables to traverse a data structure, typically from different positions.
The Core Idea
Instead of checking every pair (O(n²)), you use two pointers that move intelligently.
Visual Example
Find pair with sum = 9 in sorted array:
arr = [1, 2, 4, 5, 6, 8, 9]
Step 1: [1, 2, 4, 5, 6, 8, 9]
↑ ↑
left right
sum = 1 + 9 = 10 > 9
→ move right left
Step 2: [1, 2, 4, 5, 6, 8, 9]
↑ ↑
left right
sum = 1 + 8 = 9 ✓ Found!
Why It Works
In a sorted array:
- If sum is too large → move right pointer left
- If sum is too small → move left pointer right
This eliminates half the possibilities each step.
Time Complexity
O(n) - each pointer moves at most n times.
When to Use
- Sorted array problems
- Palindrome checking
- Pair problems (two sum, three sum)
- Remove duplicates
- Merge sorted arrays
Two Pointer Patterns
Pattern 1: Opposite Ends
Start from both ends and move inward.
// Check if string is palindrome
boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
Pattern 2: Same Direction (Fast/Slow)
Both start from same position, move at different speeds.
// Remove duplicates from sorted array
int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
Pattern 3: Partition
Partition array based on condition.
// Move all zeros to end
void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != 0) {
swap(nums, slow, fast);
slow++;
}
}
}
Pattern 4: Two Arrays
Use pointers on two different arrays.
// Merge sorted arrays
void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p--] = nums1[p1--];
} else {
nums1[p--] = nums2[p2--];
}
}
while (p2 >= 0) {
nums1[p--] = nums2[p2--];
}
}
Pattern 5: Three Pointers
// Three Sum
List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
Classic Two Pointer Problems
1. Valid Palindrome (LeetCode 125)
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
// Time: O(n), Space: O(1)
2. Two Sum II (LeetCode 167)
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[] {left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[] {};
}
// Time: O(n), Space: O(1)
3. Container With Most Water (LeetCode 11)
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxWater = 0;
while (left < right) {
int water = Math.min(height[left], height[right]) * (right - left);
maxWater = Math.max(maxWater, water);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
// Time: O(n), Space: O(1)
4. Trapping Rain Water (LeetCode 42)
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
// Time: O(n), Space: O(1)
5. Remove Duplicates (LeetCode 26)
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
// Time: O(n), Space: O(1)
Edge Cases and Tips
Common Edge Cases
- Empty array
if (nums.length == 0) return 0;
- Single element
if (nums.length == 1) return specialValue;
- All same elements
// For duplicate removal, this should return 1
- No valid pair exists
return new int[] {}; // or -1, or false
- Integer overflow
// Use long for sums: long sum = (long)nums[left] + nums[right];
Tips for Success
Identify the pattern
- Sorted array? → Opposite ends
- Remove duplicates? → Fast/Slow
- Merge? → Two arrays
Handle duplicates explicitly
while (left < right && nums[left] == nums[left + 1]) left++;
- Check bounds
while (left < right && left < nums.length && right >= 0)
- Use descriptive names
int left = 0; // not 'i'
int right = n - 1; // not 'j'
Two Pointers vs Other Techniques
| Situation | Use |
|---|---|
| Sorted array, find pair | Two Pointers |
| Unsorted array, find pair | HashMap |
| Subarray with condition | Sliding Window |
| All pairs needed | Nested Loops |
| Palindrome check | Two Pointers |
Interactive Visualization
Two Pointers Visualization
Practice Problems
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward.
Example:
Input: s = "A man, a plan, a canal: Panama"
Output: true
"amanaplanacanalpanama" is a palindrome.
Edge Cases:
- Empty string: return true
- Single character: return true
- All special characters: return true
Find two lines that together with the x-axis form a container that holds the most water.
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Maximum area is between lines at index 1 and 8.
Edge Cases:
- Two elements only
- All same height — answer is width * height
- Descending or ascending array
- First or last element is tallest
- All zeros
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
6 units of water are trapped.
Edge Cases:
- Strictly decreasing: [5,4,3,2,1] → 0
- Strictly increasing: [1,2,3,4,5] → 0
- Single bar: [5] → 0
- All equal: [3,3,3] → 0
Given a string s, return true if s is a palindrome, or false otherwise. You can delete at most one character.
Example:
Input: s = "abca"
Output: true
Delete 'c' to get palindrome.
Edge Cases:
- Already a palindrome: return true with 0 deletions
- Single character: return true
- Two different characters: return true (delete one)
Check if a string is a palindrome after removing non-alphanumeric characters.
Example:
Input: s = "A man, a plan, a canal: Panama"
Output: true
"amanaplanacanalpanama" is a palindrome.
Edge Cases:
- Empty string after filtering: return true
- Single character: return true
- All non-alphanumeric: return true
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
Example:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
The distinct triplets that sum to zero are [-1,0,1] and [-1,-1,2].
Edge Cases:
- Array with fewer than 3 elements (return empty)
- All zeros: [0,0,0] — one valid triplet
- No valid triplet exists
- Many duplicate values in the array
Quiz
1. When should you use two pointers instead of nested loops?
2. What is the time complexity of the Two Sum II solution?
3. In Container With Most Water, why do we move the shorter line?
Flashcards
Question
What are the two main two-pointer patterns?
Click to reveal answer
Answer
1) Opposite ends (start from both sides), 2) Same direction (fast/slow pointers)
Question
When can two pointers reduce O(n²) to O(n)?
Click to reveal answer
Answer
When the array is sorted and you can eliminate half the search space by moving pointers.
Question
How do you handle duplicates in Two Sum?
Click to reveal answer
Answer
Skip duplicate values: while (left < right && nums[left] == nums[left+1]) left++;
Revision Notes
Key Takeaways
- 1. Two pointers reduces O(n²) to O(n) on sorted arrays
- 2. Opposite ends for palindrome and pair problems
- 3. Fast/slow for cycle detection and duplicate removal
- 4. Always handle duplicates explicitly
- 5. Check for integer overflow with large numbers
Interview Tips
- • Ask if array is sorted before suggesting two pointers
- • Explain why moving each pointer is safe
- • Discuss time and space complexity
- • Handle edge cases explicitly
Cheat Sheet
Two Pointers Cheat Sheet
Patterns:
- Opposite Ends: left=0, right=n-1
- Fast/Slow: both start at 0, different speeds
- Partition: separate elements by condition
When to Use:
- Sorted array
- Palindrome check
- Pair problems
- Remove duplicates
Time: O(n) - each pointer moves at most n times
Space: O(1) - only two variables
Edge Cases:
- Empty array
- Single element
- No valid pair
- Integer overflow