Lesson 4 · Core algorithms

Two Pointers Technique

The Two Pointers technique optimizes nested loops into a single pass by using two variables to point to different indices in an array or string. It relies on the data having an inherent structure, like being sorted, to know which pointer to move.

Why Two Indices Beat a Nested Loop

The two pointers technique uses two indices moving through a sequence under a rule, instead of a nested loop testing every pair. Since each index advances at most n times and neither ever moves backwards, the total work is O(n) where the nested version is O(n²).

The saving is not from examining pairs faster — it is from not examining most pairs at all. Every pointer move discards a set of candidates permanently, and the technique is only correct when you can prove those discarded candidates could not have been the answer.

That proof is the part worth internalising, because it is what an examiner asks about and what makes the difference between recalling a template and understanding it. For each variant below, the question is the same: what does moving this pointer throw away, and why is that safe?

Three distinct shapes account for nearly all uses. Converging pointers start at opposite ends and move toward each other. Same-direction pointers both advance from the left at independent rates. Fast and slow pointers move at fixed different speeds through the same structure. They share only the two-index idea; the reasoning behind each differs completely.

Two indices that never retreat give O(n) instead of O(n²)
Each move permanently discards candidates — that must be justified
Converging, same-direction, and fast-slow are three separate patterns
Know what a move eliminates, not just where the pointers go

Converging Pointers

One index starts at the first element, the other at the last, and they move toward each other until they meet. This form almost always requires sorted input, because the sorting is what makes the movement rule decidable.

Pair sum is the archetype. To find two values summing to a target in a sorted array, compare the sum of the pair at the two ends against the target. If the sum is too small, the only way to increase it is to move the left pointer right — the current left value cannot pair with anything, since it is already paired with the largest remaining value and still falls short. If the sum is too large, move the right pointer left by the mirror argument. If equal, that is the answer.

That reasoning is the correctness proof, and it is short enough to state in full during an interview: each move eliminates exactly one element, and only after showing that element cannot appear in any solution. n eliminations means O(n) total.

Palindrome checking uses the same shape with a simpler rule — compare the two ends, and on a mismatch the string is not a palindrome. Reversing an array in place swaps the ends and steps inward. Container with most water is the interesting variant: the area is bounded by the shorter wall, so moving the taller one can never help, which is why the shorter side always moves.

The precondition is worth checking before reaching for it. If the array is unsorted and the problem needs indices from the original ordering, sorting destroys them — pair the values with their indices first, or use a hash map instead. Sorting to enable two pointers costs O(n log n), which is still better than O(n²) but no longer beats a single-pass hash map solution at O(n).

Requires sorted input — the ordering makes the move rule valid
Sum too small ⇒ move left; too large ⇒ move right
Each move eliminates one element with a proof it cannot be in the answer
Sorting first costs O(n log n) and may destroy original indices

Same-Direction Pointers

Here both indices start at the left and advance independently. The most useful form gives them distinct jobs: a read pointer that visits every element, and a write pointer marking where the next kept element goes.

This is how filtering works in place. Scan with the read pointer; whenever an element should survive, copy it to the write position and advance the write pointer. When the scan finishes, the first write elements are the result and everything after is stale. One pass, O(n) time and O(1) extra space.

The pattern covers a family of problems that otherwise invite repeated O(n) deletions — remove all instances of a value, remove duplicates from a sorted array, move all zeros to the end. Doing those one deletion at a time is O(n) per removal and O(n²) overall; the read-write pass does it once.

The write pointer never overtakes the read pointer, which is what makes overwriting safe: any position being written has already been read. That invariant is worth stating, since it is the reason the algorithm can modify the array it is still scanning.

A variant keeps duplicates up to k times by comparing the incoming element against arr[write − k] rather than against the immediately previous element — the same skeleton with the condition generalised.

The sliding window is the other same-direction form, where the two pointers bound a range rather than splitting responsibilities. There the left pointer advances only to restore a condition the right pointer broke, and the shared cost argument is identical: neither pointer retreats, so the total is O(n) despite the nested loop.

Read pointer visits everything; write pointer marks the next keeper
In-place filtering in O(n) time and O(1) space
Write never passes read, so overwriting is always safe
A sliding window is the same shape with the pair bounding a range

Key reference

Terms, operations, and practical uses

Core vocabulary

PointerIn this context, it's just an integer variable storing an index into an array or string.
ConvergenceWhen two pointers start at opposite ends and move toward each other until they meet.
CycleA closed loop in a data structure, typically a linked list, where traversing a path eventually leads back to a previously visited node.

Algorithms

Floyd's Tortoise and HareA cycle detection algorithm using two pointers moving at different speeds (1 step vs 2 steps).
PartitioningSeparating elements in an array based on a condition (like QuickSort's partition) using read and write pointers.
Two Sum (Sorted)Finding two elements that sum to a target in a sorted array by moving endpoints inward based on the current sum.

Best practices

BoundariesAlways ensure pointers stay within the array bounds (e.g., left >= 0 and right < length).
TerminationBe precise about whether the loop should end when left == right or left > right depending on if the middle element matters.
Sorting FirstMany two-pointer techniques require the input to be sorted. Account for the O(N log N) sorting time in your complexity analysis.

Implementation

Reverse an array in place

def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
letters = ['a', 'b', 'c', 'd', 'e']
reverse_array(letters)
print(letters)

#include <iostream>
#include <vector>
using namespace std;
void reverseArray(vector<char>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        swap(arr[left], arr[right]);
        left++;
        right--;
    }
}
int main() {
    vector<char> letters = {'a', 'b', 'c', 'd', 'e'};
    reverseArray(letters);
    cout << '[';
    for (size_t i = 0; i < letters.size(); i++) {
        if (i) cout << ", ";
        cout << '\'' << letters[i] << '\'';
    }
    cout << "]\n";
}

public class Main {
    static void reverseArray(char[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
    public static void main(String[] args) {
        char[] letters = {'a', 'b', 'c', 'd', 'e'};
        reverseArray(letters);
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < letters.length; i++) {
            if (i > 0) sb.append(", ");
            sb.append('\'').append(letters[i]).append('\'');
        }
        System.out.println(sb.append("]"));
    }
}

Watch it run

Step through it

Running on array = ['a', 'b', 'c', 'd', 'e']

Output

Read all 7 Steps

Initialize pointers Place left at index 0 and right at the last index 4.
Swap ends Swap elements at left and right: 'a' and 'e'.
Move pointers Increment left to 1, decrement right to 3.
Swap next pair Swap elements at left and right: 'b' and 'd'.
Move pointers Increment left to 2, decrement right to 2.
Check overlap left is 2, right is 2. The loop condition (left < right) is false.
Done The array is fully reversed in place without requiring an additional array.

Fast and Slow Pointers

The third form advances two pointers through the same structure at fixed different speeds, typically one step and two steps per iteration. Rather than searching for a value, this extracts structural facts, and it is the standard tool on linked lists where indexing is unavailable.

Finding the midpoint: run until the fast pointer reaches the end. Having covered twice the distance, the slow pointer is at the middle. On an even-length list, which of the two middle elements you land on depends on whether the loop tests fast or fast.next first — worth pinning down deliberately, since merge sort's split depends on it.

Cycle detection — Floyd's tortoise and hare — is the same loop, comparing the pointers each step. If the fast pointer reaches null the structure terminates and there is no cycle. If a cycle exists, the fast pointer must enter it, and thereafter closes the gap on the slow pointer by exactly one node per iteration, so the gap shrinks monotonically and a meeting is guaranteed, not merely likely.

That gap-closes-by-one argument is the part that turns the algorithm from a trick into a proof, and it is what distinguishes a complete exam answer. It also explains why a speed ratio of 1 and 2 is used: any larger gap change could skip past the slow pointer without landing on it in a short cycle.

Finding the cycle's start: after the meeting, reset one pointer to the head and advance both one step at a time. Their next meeting is the entry node, because the distance from the head to the entry equals the distance from the meeting point to the entry measured around the loop.

Nth node from the end uses a fixed gap instead of a speed difference: advance one pointer n steps, then move both together until the leader hits null. The trailer is on the answer. It solves in one pass what would otherwise take two — one to count the length, one to walk back in.

The same idea escapes linked lists entirely. Applied to a function iterated on itself, x → f(x), it detects cycles in O(1) memory, which is the basis of Pollard's rho factorisation and of finding a duplicate in an array where values index into it.

The three patterns and what each requires
Pattern	Start	Requires	Typical use
Converging	Opposite ends	Sorted data	Pair sum, palindrome, container
Same-direction	Both at the left	Nothing	In-place filtering, sliding window
Fast and slow	Both at the start	A traversable chain	Midpoint, cycle detection

Fast moves 2, slow moves 1 — one pass, O(1) space
The gap closes by exactly one per step, so meeting is guaranteed
Reset to the head after meeting to locate the cycle entrance
A fixed gap of n finds the nth node from the end in one pass