Two Pointers Technique

When to Use Two Pointers?

• You need to search for a pair or subarray with a given property (e.g., sum = target)
• You need to perform in-place operations (like reversing or removing elements)
• You need to compare elements from both ends (e.g., palindrome checks)

Common Types of Two Pointers

• Opposite Direction: One pointer starts from the beginning, another from the end. Used for pair finding, reversal, etc.
• Same Direction: Both pointers move from the start. Often used in sliding window problems.

Example 1: Check if Array Has a Pair with Given Sum

Problem Statement: You are given a sorted array of integers and a target sum. Your task is to check whether there exists a pair of numbers in the array whose sum is equal to the target.

Why Use Two Pointers?

Since the array is sorted, we can avoid using nested loops (which would take O(n²) time) by using the two pointers technique to reduce the time complexity to O(n).

The idea is to place one pointer at the start of the array and the other at the end. We move the pointers inward based on the current sum:

• If the sum is too small, move the left pointer to the right to increase the sum.
• If the sum is too large, move the right pointer to the left to decrease the sum.
• If the sum equals the target, we've found our pair!

Pseudocode

// Input: sorted array and target sum
left = 0
right = array.length - 1

while (left < right):
    sum = array[left] + array[right]
    if (sum == target):
        return true
    else if (sum < target):
        left += 1
    else:
        right -= 1

return false

Dry Run with Sample Input

Input:

array = [1, 2, 3, 4, 6, 8, 11]
target = 10

left	right	array[left]	array[right]	sum	Action
0	6	1	11	12	Sum > 10 → Decrease right
0	5	1	8	9	Sum < 10 → Increase left
1	5	2	8	10	Sum = 10 → Found!

Result: True (Pair found: 2 and 8)

Step-by-Step Explanation

1. Start with left = 0 and right = 6 (pointing to 1 and 11).
2. Sum = 1 + 11 = 12. Too big → move right left (to 8).
3. Now sum = 1 + 8 = 9. Too small → move left right (to 2).
4. Now sum = 2 + 8 = 10 → Target found!

Time and Space Complexity

• Time Complexity: O(n) — Each pointer moves at most n times.
• Space Complexity: O(1) — Only a few variables used, no extra data structures.

Why This Works Only on Sorted Arrays?

Two pointers rely on the ability to determine whether to increase or decrease the sum by moving a pointer. That only works when the array is sorted — otherwise, increasing or decreasing a pointer won't have predictable effects on the sum.

The two pointers technique is a simple yet powerful way to avoid nested loops and get a linear time solution. It takes advantage of the sorted property to move intelligently and find the answer efficiently.

left = 0
right = array.length - 1

while (left < right):
    swap(array[left], array[right])
    left += 1
    right -= 1

array = [10, 20, 30, 40, 50]

[50, 40, 30, 20, 10]

Example 3: Remove Duplicates from Sorted Array

Problem: Given a sorted array, remove the duplicates in-place so that each element appears only once and return the new length of the array. The relative order of the elements should be kept the same, and you should not use extra space (O(1) space).

Why Two Pointers?

This is a classic case for the Two Pointers Technique. The idea is simple but very efficient:

• Use one pointer (i) to keep track of the last unique element (also called the "slow" pointer).
• Use the second pointer (j) to scan the array for the next unique element (also called the "fast" pointer).

Since the array is already sorted, duplicates will always be adjacent. So, we can move the fast pointer and compare each element with the last unique value.

When we find a new unique element, we increment the slow pointer and overwrite the duplicate position with the new unique value.

Pseudocode

if array is empty:
    return 0

i = 0  // slow pointer

for j from 1 to array.length - 1:
    if array[j] != array[i]:
        i += 1
        array[i] = array[j]

return i + 1

Step-by-Step Dry Run

Let's walk through an example:

Input: [10, 10, 20, 20, 30, 40, 40]

j (fast)	i (slow)	array[j]	array[i]	Action	Array State
1	0	10	10	Duplicate → skip	[10, 10, 20, 20, 30, 40, 40]
2	0	20	10	New value → i++ → array[1] = 20	[10, 20, 20, 20, 30, 40, 40]
3	1	20	20	Duplicate → skip	[10, 20, 20, 20, 30, 40, 40]
4	1	30	20	New value → i++ → array[2] = 30	[10, 20, 30, 20, 30, 40, 40]
5	2	40	30	New value → i++ → array[3] = 40	[10, 20, 30, 40, 30, 40, 40]
6	3	40	40	Duplicate → skip	[10, 20, 30, 40, 30, 40, 40]

Final value of i: 3

New length: i + 1 = 4

Modified Array: [10, 20, 30, 40] (first 4 elements)

Explanation

• i always points to the last unique value found.
• j explores the array to find the next non-duplicate value.
• When a new unique value is found, we increment i and copy array[j] to array[i].

Time and Space Complexity

• Time Complexity: O(n) — one pass through the array.
• Space Complexity: O(1) — in-place update, no extra storage used.

Why Two Pointers Works Here

By separating the roles of the two pointers:

• The slow pointer tracks the position of the next unique value to be placed.
• The fast pointer scans for upcoming unique values.

This method ensures no duplicate is placed in the first part of the array, and the array is modified in-place with minimal code.

Limitations

• Works best on sorted arrays or data structures where order can be exploited.
• Requires careful index management to avoid bugs.
• Not suitable for problems that require random access across the array.

Conclusion

The Two Pointers Technique is a simple yet powerful strategy in DSA. It offers elegant solutions to a variety of problems with linear time complexity. Once you learn to spot scenarios where two pointers can be applied, you'll find your problem-solving speed and accuracy improving significantly.