Two Pointer - Introduction

Two Pointer Technique – Introduction

The two pointer technique is a problem-solving pattern in which two indices are used to track different positions in an array, string, or linked structure.

Instead of exploring every possible pair or repeatedly scanning the same elements, the pointers move according to a condition and gradually eliminate candidates that cannot contribute to the answer.

The pointers may:

• Start at opposite ends and move toward each other.

• Start together and move at different speeds.

• Represent the beginning and end of a valid range.

• Separate processed and unprocessed elements.

• Track two different arrays during merging or comparison.

The technique is especially useful when pointer movement allows us to make a safe decision about which possibilities can be ignored.

What Problem Does the Two Pointer Technique Solve?

Many array and string problems initially appear to require nested loops.

Suppose an array contains N elements and we need to examine every pair.

The first element may be paired with N - 1 other elements. The second may be paired with N - 2 remaining elements, and so on.

The total number of pairs is:

N × (N - 1) / 2

Therefore, examining every pair requires:

O(N²) time

This approach becomes inefficient as the input grows.

Two pointers improve such problems when the input provides an order or relationship that lets us discard several possibilities after one comparison.

For example, in a sorted array:

• If the current pair sum is too small, moving the right pointer left would make the sum even smaller or unchanged. Therefore, the left pointer must move forward.

• If the current pair sum is too large, moving the left pointer forward would make it even larger or unchanged. Therefore, the right pointer must move backward.

Each decision removes a complete group of impossible pairs rather than checking them individually.

The Core Requirement: Safe Elimination

Two pointers do not improve every problem automatically.

The technique works when a pointer movement can safely eliminate candidates.

After checking the current state, we should be able to answer:

• Why can the left pointer move?

• Why can the right pointer move?

• Which possibilities become impossible after that movement?

• Can a discarded possibility ever become a valid answer later?

If pointer movement may discard a possible answer, the technique is not correct.

For pair sum, sorted order provides safe elimination. Without sorted order, a small sum does not tell us which pointer should move because the next value may be smaller or larger unpredictably.

Therefore, two pointers rely on more than using two index variables. They rely on a movement rule that preserves correctness.

How Two Pointers Reduce Repeated Work

A nested-loop solution often restarts the inner search for every new outer position.

Two pointers retain information from the previous comparison.

After one pointer moves:

• The other pointer keeps its useful position.

• Previously rejected candidates are not checked again.

• The search range becomes smaller.

• Both pointers continue only in their allowed direction.

In many two-pointer solutions, each pointer crosses the input at most once.

Therefore, the total movement is proportional to:

N + N = 2N

After ignoring the constant factor:

Time Complexity = O(N)

Main Two Pointer Patterns

The movement of the two pointers depends on the problem.

Opposite-Direction Pointers

One pointer begins at the start and the other at the end.

They move toward each other.

This pattern is useful for:

• Pair sum in a sorted array

• Reversing an array

• Palindrome checking

• Container problems

• Comparing elements from both ends

The usual initialization is:

left = 0

right = N - 1

Traversal continues while:

left < right

Same-Direction Pointers

Both pointers move from left to right.

One pointer may represent the current element, while the other represents the next position where a valid element should be placed.

This pattern is useful for:

• Removing duplicates from a sorted array

• Moving zeros

• Partitioning an array

• Merging sorted arrays

• Filtering elements in place

The pointers do not need to move together. One may advance during every iteration while the other moves only after a useful element is found.

Fast and Slow Pointers

Both pointers begin near the same position, but the fast pointer moves more quickly.

This pattern is commonly used for:

• Detecting cycles in a linked list

• Finding the middle of a linked list

• Locating a cycle’s starting point

• Checking repeated state transitions

The distance between the pointers provides information about the structure being traversed.

Window-Boundary Pointers

The pointers represent the left and right boundaries of a contiguous range.

The right pointer expands the range, while the left pointer removes elements when required.

This pattern is usually studied separately as the sliding window technique.

Choosing the Pointer Movement

The most important part of a two-pointer solution is deciding which pointer should move.

A pointer should move only when the current comparison proves that some candidates can no longer produce the answer.

Common movement rules include:

The movement rule must come from the problem’s property, not from memorizing a fixed template.

Checking Pair Sum in a Sorted Array

Given a sorted array and a target, determine whether two different elements have a sum equal to the target.

Consider:

arr = [1, 2, 4, 6, 10]

target = 8

Place:

left = 0

right = 4

The sorted order tells us how the sum will change:

• Moving left forward increases or preserves the left value.

• Moving right backward decreases or preserves the right value.

This allows the search to discard impossible pairs safely.

Algorithm

• Initialize left at the first element and right at the last element because the array is sorted.

• Calculate the sum of the values at both pointers.

• Return true if the sum equals the target because a valid pair has been found.

• Move left forward when the sum is too small because a larger value is required.

• Move right backward when the sum is too large because a smaller value is required.

• Continue until the pointers meet; return false if no valid pair is found.

Time Complexity: O(N) because each pointer moves across the array at most once.

Space Complexity: O(1) because only two pointer variables are maintained.

Why Is Sorted Order Necessary for Pair Sum?

Suppose the current sum is smaller than the target.

In a sorted array, moving left forward gives us an equal or larger value. This is the only movement that can increase the sum while keeping right fixed.

Similarly, when the sum is too large, moving right backward gives us an equal or smaller value.

In an unsorted array, neither movement is predictable. The next value may increase or decrease the sum.

For an unsorted pair-sum problem, common alternatives are:

• Use a hash set in O(N) time and O(N) space.

• Sort the array in O(N log N) time and then apply two pointers.

• Check every pair in O(N²) time when constraints are small.

Sorting may also change the original indices, so preserve them if the problem asks for index positions.

Reversing an Array Using Two Pointers

Two pointers can reverse an array in place by swapping elements from opposite ends.

Consider:

arr = [1, 2, 3, 4, 5]

Initialize:

left = 0

right = 4

Every swap places two elements into their final reversed positions.

Algorithm

• Initialize left at the first element and right at the last element.

• Swap the values at both pointers because they occupy mirrored positions in the reversed array.

• Move left one position forward and right one position backward.

• Repeat the swapping and movement while left is smaller than right.

• Stop when the pointers meet or cross because every outer pair has reached its final position.

• Return or use the modified array.

Time Complexity: O(N) because approximately half of the elements are swapped, and every element is handled at most once.

Space Complexity: O(1) because reversal is performed in place.

Checking Whether a String Is a Palindrome

A palindrome reads the same from left to right and right to left.

Two pointers can compare corresponding characters from both ends.

Consider:

s = "level"

Initialize:

left = 0

right = 4

The string is a palindrome only if every mirrored pair matches.

Algorithm

• Initialize left at the first character and right at the last character.

• Compare the characters at both pointers because they occupy mirrored positions.

• Return false immediately if the characters differ because the string cannot be a palindrome.

• Move both pointers inward when the characters match.

• Continue until the pointers meet or cross.

• Return true because every mirrored pair has matched.

Time Complexity: O(N) because at most half of the character pairs are compared.

Space Complexity: O(1) because only the two pointers are used.

In-Place Modification with Two Pointers

Two pointers are frequently used to modify an array without creating another array.

One pointer scans the input, while the other marks where the next accepted value should be placed.

For example, while moving zeros to the end:

• The fast pointer searches for non-zero values.

• The slow pointer marks the first position that should contain a non-zero value.

• When the fast pointer finds one, it is moved or swapped into the slow position.

• The slow pointer advances only after a value is placed correctly.

This reduces additional storage from O(N) to O(1) in problems where in-place modification is allowed.

When Should You Consider Two Pointers?

Consider the two pointer technique when:

• The problem involves pairs in a sorted array.

• Elements must be compared from opposite ends.

• An array or string must be reversed.

• The problem asks for an in-place modification.

• Two sorted inputs must be merged.

• Duplicate values must be removed from sorted data.

• A contiguous range expands or shrinks.

• A linked list requires cycle detection or middle-node discovery.

• Pointer movement can safely eliminate candidates.

A useful recognition question is:

After checking the current positions, can one pointer move without losing a possible answer?

If yes, a two-pointer solution may be appropriate.

When Two Pointers May Not Work

Two pointers may not be suitable when:

• The input has no order that supports safe movement.

• A pointer may need to move backward after moving forward.

• Discarded elements may become useful later.

• The problem involves non-contiguous combinations.

• The condition does not change predictably as pointers move.

• Additional history is required to make the next decision.

For example, the opposite-end pair-sum method cannot be applied directly to an unsorted array because the sum does not change predictably after either pointer moves.

Advantages of Two Pointers

• It can reduce some nested-loop solutions from O(N²) to O(N).

• It avoids repeated comparisons.

• It often requires only O(1) auxiliary space.

• It supports in-place array modification.

• It works naturally with sorted arrays and strings.

• It can express range boundaries clearly.

• It combines with sorting, hashing, and sliding window techniques.

Common Mistakes

• Applying opposite-end pair sum to an unsorted array.

• Moving the wrong pointer after comparing the current sum with the target.

• Using left <= right when the problem requires two different elements.

• Forgetting to move both pointers after a successful swap.

• Returning true before confirming that two different indices are used.

• Losing original indices after sorting an array.

• Moving a pointer without reversing the outgoing element’s contribution.

• Treating every problem containing two indices as a two-pointer problem.

• Assuming every two-pointer solution automatically takes O(N) time.

• Forgetting to define how punctuation and letter case are handled in palindrome problems.

FAQs

Q1. Does using two pointers always reduce the time complexity to O(N)?

No. The complexity depends on how the pointers move and what work is performed during each movement. Linear time is achieved when both pointers move only forward or inward and each position is processed a constant number of times.

Q2. Why does the opposite-end pair-sum method require a sorted array?

Sorted order makes the effect of pointer movement predictable. Moving left increases the possible sum, while moving right decreases it, allowing impossible pairs to be discarded safely.

Q3. Can two pointers be used on an unsorted array?

Yes, for tasks such as partitioning or moving zeros. However, opposite-end pair searching usually requires sorting first or using a hash-based method.

Q4. What is the difference between two pointers and sliding window?

Two pointers is the broader pattern of maintaining two positions. Sliding window is a specialized two-pointer pattern in which the pointers represent the boundaries of a contiguous range.

Q5. How should spaces, punctuation, and letter case be handled in palindrome problems?

Follow the problem statement. If non-alphanumeric characters must be ignored, move the pointers past them before comparison. If comparison is case-insensitive, normalize the characters before checking equality.