Suppose you have a sorted array and someone asks you: "Is there a pair of numbers that adds up to 10?"
1, 3, 4, 6, 8, 11The first idea most people have is to try every pair:
(1,3) (1,4) (1,6) (1,8) (1,11)
(3,4) (3,6) (3,8) (3,11)
...That works, but it takes O(n²) time. For an array with one lakh elements, that is about 5 billion pairs.
There is a much smarter way. Put one finger on the first element and another finger on the last element, then move the fingers towards each other based on what you see. You will find the answer in a single pass.
This simple idea is called the Two Pointers Technique, and it is one of the most frequently used patterns in coding interviews.
What is the Two Pointers Technique?
The two pointers technique uses two index variables that move through an array (or string) in a controlled way, so that we can solve a problem in one pass instead of checking every pair.
The word "pointer" here does not mean a C-style memory pointer. It simply means a variable that stores an index, such as left, right, slow or fast.
The key idea is that every step throws away some possibilities we no longer need to check. Because each pointer only moves forward (or only backward), the total number of steps is at most about n.
There are three common patterns:
Pattern | How the pointers move | Typical problems |
|---|---|---|
Opposite ends | One starts at the beginning, one at the end, they move towards each other | Pair sum in sorted array, reverse, palindrome, container with most water |
Same direction (slow and fast) | Both start at the beginning, the fast one scans, the slow one marks where to write | Remove duplicates, move zeroes, partitioning |
Two arrays | One pointer in each array | Merge two sorted arrays, intersection of sorted arrays |
Let's look at each pattern one by one.
Pattern 1: Opposite Ends
In this pattern, we start with:
left → first index (0)
right → last index (n - 1)and keep moving them towards each other until they meet.
left right
↓ ↓
[ 1 , 3 , 4 , 6 , 8 , 11 ]Example: Pair with a Given Sum
Problem: Given a sorted array and a target, find two numbers whose sum is equal to the target.
Let's use target = 10 and the array:
Index: 0 1 2 3 4 5
Value: 1 3 4 6 8 11At each step we look at arr[left] + arr[right]:
If the sum is equal to the target, we found the pair.
If the sum is too small, we need a bigger number, so we move
leftforward.If the sum is too big, we need a smaller number, so we move
rightbackward.
Step by step:
Step 1: left=0 (1), right=5 (11) → 1 + 11 = 12 > 10 → right--
Step 2: left=0 (1), right=4 (8) → 1 + 8 = 9 < 10 → left++
Step 3: left=1 (3), right=4 (8) → 3 + 8 = 11 > 10 → right--
Step 4: left=1 (3), right=3 (6) → 3 + 6 = 9 < 10 → left++
Step 5: left=2 (4), right=3 (6) → 4 + 6 = 10 = 10 → Found!Only 5 steps instead of checking all 15 pairs.
Why Is It Safe to Move a Pointer?
This is the part interviewers love to ask about.
In Step 1, the sum 1 + 11 = 12 is too big. Since the array is sorted, 11 is the largest value. Pairing 11 with any other element (all of which are at least 1) will give a sum of at least 12. So 11 can never be part of the answer, and we can safely drop it by doing right--.
Similarly, when the sum is too small, the current arr[left] is too small even with the largest remaining value, so it can never be part of the answer. We drop it with left++.
Every move eliminates one element that cannot possibly be part of the answer. That is why two pointers never misses a valid pair.
This reasoning depends completely on the array being sorted. On an unsorted array, this approach does not work.
Pair Sum in Java
class Main {
static int[] pairWithSum(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
return new int[] {left, right};
}
else if (sum < target) {
left++;
}
else {
right--;
}
}
return new int[] {-1, -1};
}
public static void main(String[] args) {
int[] arr = {1, 3, 4, 6, 8, 11};
int[] result = pairWithSum(arr, 10);
System.out.println("Indexes: " + result[0] + ", " + result[1]);
System.out.println("Values: " + arr[result[0]] + " + " + arr[result[1]]);
int[] none = pairWithSum(arr, 100);
System.out.println("Target 100: " + none[0] + ", " + none[1]);
}
}Output:
Indexes: 2, 3
Values: 4 + 6
Target 100: -1, -1Time complexity is O(n) because each step moves one pointer, and the pointers can move at most n times in total. Space complexity is O(1).
If the input array is not sorted, you can first sort it with Arrays.sort() (which costs O(n log n)), but remember that sorting changes the original indexes.
Example: Reverse an Array and Check a Palindrome
Reversing an array is the simplest opposite-ends problem. Swap arr[left] and arr[right], then move both pointers inward:
[10, 20, 30, 40, 50] swap 10 and 50
[50, 20, 30, 40, 10] swap 20 and 40
[50, 40, 30, 20, 10] left == right → stopYou already saw palindrome checking in the Strings chapter. Here is a slightly harder interview version: ignore spaces and punctuation, and ignore case. Two pointers handle this neatly by simply skipping characters that are not letters or digits.
class Main {
static void reverse(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
static boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
char a = s.charAt(left);
char b = s.charAt(right);
if (!Character.isLetterOrDigit(a)) {
left++;
}
else if (!Character.isLetterOrDigit(b)) {
right--;
}
else {
if (Character.toLowerCase(a) != Character.toLowerCase(b)) {
return false;
}
left++;
right--;
}
}
return true;
}
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
reverse(arr);
System.out.println(java.util.Arrays.toString(arr));
System.out.println(isPalindrome("racecar"));
System.out.println(isPalindrome("A man, a plan, a canal: Panama"));
System.out.println(isPalindrome("hello"));
}
}Output:
[50, 40, 30, 20, 10]
true
true
falseNotice the loop condition left < right. When the pointers meet (odd length) or cross (even length), every character has been compared.
Example: Container With Most Water
This is a famous interview problem.
Problem: You are given an array height, where each value is the height of a vertical line. Choose two lines that, together with the x-axis, hold the most water.
The water held between lines i and j is:
area = (j - i) × min(height[i], height[j])Start with the widest possible container (left = 0, right = n - 1). Now, which pointer should we move?
The area is limited by the shorter line. If we move the taller line inward, the width decreases and the height can never become bigger than the shorter line, so the area can never get better. The only chance of a bigger area is to move the shorter line and hope for a taller one.
class Main {
static int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int best = 0;
while (left < right) {
int width = right - left;
int h = Math.min(height[left], height[right]);
best = Math.max(best, width * h);
if (height[left] < height[right]) {
left++;
}
else {
right--;
}
}
return best;
}
public static void main(String[] args) {
int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
System.out.println("Max water: " + maxArea(height));
}
}Output:
Max water: 49The best container uses the lines at index 1 (height 8) and index 8 (height 7): width 7 × height 7 = 49.
Pattern 2: Same Direction (Slow and Fast)
In this pattern, both pointers start at the left side:
fastscans every element.slowmarks the position where the next "good" element should be written.
This lets us modify an array in place without using an extra array.
Example: Remove Duplicates from a Sorted Array
Problem: Given a sorted array, remove the duplicates in place so that each value appears once, and return the number of unique values.
Because the array is sorted, duplicates are always next to each other. So we only need to compare arr[fast] with the last unique value arr[slow].
arr = [1, 1, 2, 2, 2, 3, 4, 4]
slow=0, fast=1: arr[1]=1 equals arr[0]=1 → skip
slow=0, fast=2: arr[2]=2 is new → slow=1, arr[1]=2
slow=1, fast=3: 2 equals 2 → skip
slow=1, fast=4: 2 equals 2 → skip
slow=1, fast=5: 3 is new → slow=2, arr[2]=3
slow=2, fast=6: 4 is new → slow=3, arr[3]=4
slow=3, fast=7: 4 equals 4 → skip
Unique count = slow + 1 = 4import java.util.Arrays;
class Main {
static int removeDuplicates(int[] arr) {
if (arr.length == 0) {
return 0;
}
int slow = 0;
for (int fast = 1; fast < arr.length; fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1;
}
public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 2, 3, 4, 4};
int k = removeDuplicates(arr);
System.out.println("Unique count: " + k);
System.out.println("First k elements: " + Arrays.toString(Arrays.copyOf(arr, k)));
System.out.println("Whole array: " + Arrays.toString(arr));
}
}Output:
Unique count: 4
First k elements: [1, 2, 3, 4]
Whole array: [1, 2, 3, 4, 2, 3, 4, 4]Only the first k elements matter. The values after that are leftovers, and that is completely normal for in-place problems.
Example: Move Zeroes
Problem: Move all the zeroes to the end of the array while keeping the order of the non-zero elements. Do it in place.
Whenever fast finds a non-zero value, we swap it into position slow and move slow forward. All non-zero values end up at the front in their original order, and the zeroes get pushed to the back.
import java.util.Arrays;
class Main {
static void moveZeroes(int[] arr) {
int slow = 0;
for (int fast = 0; fast < arr.length; fast++) {
if (arr[fast] != 0) {
int temp = arr[slow];
arr[slow] = arr[fast];
arr[fast] = temp;
slow++;
}
}
}
public static void main(String[] args) {
int[] arr = {0, 1, 0, 3, 12};
moveZeroes(arr);
System.out.println(Arrays.toString(arr));
}
}Output:
[1, 3, 12, 0, 0]Both of these problems run in O(n) time and O(1) extra space.
The slow and fast idea also appears in linked lists, where a slow pointer moves one step and a fast pointer moves two steps. You will see that version (for finding the middle node and detecting cycles) in the Linked List chapter.
Pattern 3: Two Arrays
Sometimes we have two sorted arrays and we keep one pointer in each.
Example: Merge Two Sorted Arrays
At each step, compare the current elements of both arrays, copy the smaller one into the result, and move that array's pointer forward.
a = [1, 4, 7, 10] b = [2, 3, 8]
i j
1 vs 2 → take 1 result: [1]
4 vs 2 → take 2 result: [1, 2]
4 vs 3 → take 3 result: [1, 2, 3]
4 vs 8 → take 4 result: [1, 2, 3, 4]
7 vs 8 → take 7 result: [1, 2, 3, 4, 7]
10 vs 8 → take 8 result: [1, 2, 3, 4, 7, 8]
b is finished → copy the rest of a: [1, 2, 3, 4, 7, 8, 10]import java.util.Arrays;
class Main {
static int[] mergeSorted(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int i = 0;
int j = 0;
int k = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) {
result[k++] = a[i++];
}
else {
result[k++] = b[j++];
}
}
while (i < a.length) {
result[k++] = a[i++];
}
while (j < b.length) {
result[k++] = b[j++];
}
return result;
}
public static void main(String[] args) {
int[] a = {1, 4, 7, 10};
int[] b = {2, 3, 8};
System.out.println(Arrays.toString(mergeSorted(a, b)));
}
}Output:
[1, 2, 3, 4, 7, 8, 10]This takes O(n + m) time, where n and m are the lengths of the two arrays. This exact merge step is the heart of Merge Sort, which you saw in the Merge Sort chapter.
Going Further: Three Sum
Two pointers can also be combined with a loop to solve harder problems.
Problem: Find all unique triplets in the array that add up to 0.
The idea:
Sort the array.
Fix the first number
nums[i]using a loop.For the rest of the array, use opposite-end two pointers to find pairs that sum to
-nums[i].Skip repeated values so the same triplet is not added twice.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Main {
static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicate values for the first number
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int 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]));
left++;
right--;
// Skip duplicate values for the second number
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
}
else if (sum < 0) {
left++;
}
else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
System.out.println(threeSum(nums));
}
}Output:
[[-1, -1, 2], [-1, 0, 1]]The sorting takes O(n log n), and for each i the two-pointer scan takes O(n), so the total time is O(n²). That is much better than the brute-force O(n³) approach of trying every triplet.
The duplicate-skipping lines are where most people make mistakes. Without them, the input [-1, 0, 1, 2, -1, -4] would report [-1, 0, 1] twice.
Time and Space Complexity
Problem | Brute Force | Two Pointers | Extra Space |
|---|---|---|---|
Pair sum (sorted) |
|
|
|
Reverse / palindrome | - |
|
|
Remove duplicates (sorted) |
|
|
|
Container with most water |
|
|
|
Merge two sorted arrays | - |
|
|
Three sum |
|
|
|
Why is two pointers usually O(n) even though it has a while loop that runs many times? Because each iteration moves at least one pointer, and a pointer never moves back. The pointers together can only travel about n positions, so the loop runs at most about n times.
How to Recognise a Two Pointers Problem
Think about two pointers when you see:
A sorted array (or one you are allowed to sort) and a question about pairs or triplets with a certain sum.
A request to do something in place with
O(1)extra space (remove, move, partition).Comparing elements from both ends (palindromes, reversing).
Two sorted sequences that need to be merged or compared.
A brute-force solution with two nested loops where you can argue that one choice eliminates many others.
Common Mistakes
1. Using Two Pointers on an Unsorted Array
The opposite-ends pair-sum logic only works because the array is sorted. On [8, 1, 6, 3], moving right-- because the sum is too big may throw away the element you needed. Either sort first, or use a different approach (for example, a HashMap, which you will learn later).
2. Wrong Loop Condition
For pair problems, use while (left < right). Using left <= right lets both pointers point at the same element, which means you may pair an element with itself.
3. Forgetting to Move a Pointer
If some branch of your loop does not change left or right, the loop runs forever. In the palindrome example, every branch moves at least one pointer.
4. Not Handling Duplicates
In problems that ask for unique pairs or triplets, you must skip repeated values after finding an answer, as shown in Three Sum.
5. Moving the Wrong Pointer
In Container With Most Water, moving the taller line is a classic bug. Always ask: "Which pointer can never be part of a better answer?" That is the one to move.
Two Pointers vs Other Techniques
Technique | Best for | Needs sorted input? |
|---|---|---|
Two Pointers | Pairs, in-place rearranging, merging, comparing both ends | Often (for sum problems) |
Sliding Window | Contiguous subarrays or substrings | No |
Binary Search | Finding one target or boundary | Yes |
Hashing | Pair sum in an unsorted array, counting | No, but uses extra memory |
The Sliding Window technique, which you will learn in the next chapter, is actually a special form of same-direction two pointers, where the two pointers mark the start and end of a window.
Practice Problems
Try these popular problems to build confidence:
Two Sum II - Input Array Is Sorted
Valid Palindrome
Reverse String
Remove Duplicates from Sorted Array
Move Zeroes
Squares of a Sorted Array
Merge Sorted Array
Container With Most Water
3Sum
Sort Colors (Dutch National Flag problem)
The Main Idea
The two pointers technique uses two indexes that move through the data in a controlled way, so that a problem which looks like it needs nested loops can often be solved in a single pass.
Remember the three patterns:
Opposite ends → left = 0, right = n - 1, move towards each other
Slow and fast → both start at 0, fast scans, slow writes
Two arrays → one pointer in each sorted arrayAnd the key reason it works:
Each move throws away an element that can never be part of the answer.Two pointers turns many O(n²) brute-force solutions into O(n) solutions with O(1) extra space, especially when the input is sorted.