Chapter 21 of 65

Two Pointers Technique

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, 11

The 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   11

At 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 left forward.

  • If the sum is too big, we need a smaller number, so we move right backward.

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, -1

Time 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 → stop

You 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
false

Notice 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: 49

The 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:

  • fast scans every element.

  • slow marks 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 = 4
import 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:

  1. Sort the array.

  2. Fix the first number nums[i] using a loop.

  3. For the rest of the array, use opposite-end two pointers to find pairs that sum to -nums[i].

  4. 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)

O(n²)

O(n)

O(1)

Reverse / palindrome

-

O(n)

O(1)

Remove duplicates (sorted)

O(n) with extra array

O(n)

O(1)

Container with most water

O(n²)

O(n)

O(1)

Merge two sorted arrays

-

O(n + m)

O(n + m) for the result

Three sum

O(n³)

O(n²)

O(1) apart from the output (sorting may use some extra space internally)

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:

  1. Two Sum II - Input Array Is Sorted

  2. Valid Palindrome

  3. Reverse String

  4. Remove Duplicates from Sorted Array

  5. Move Zeroes

  6. Squares of a Sorted Array

  7. Merge Sorted Array

  8. Container With Most Water

  9. 3Sum

  10. 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 array

And 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.