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.

Converging pointers

Starting pointers at opposite ends and moving them inwards is a classic approach for sorted arrays. A typical use case is finding a pair of numbers that sum to a target. If the sum is too small, advance the left pointer to increase the sum. If it's too large, decrease the right pointer.

This method avoids evaluating all pairs, skipping impossible combinations because of the sorted property.

Start at 0 and length-1
Only works if the array is sorted
O(N) time and O(1) space

Same-direction pointers

Pointers can start at the same end and move in the same direction but at different rates or under different conditions. This is often used for removing duplicates in place or segregating elements.

One pointer keeps track of the 'last valid' position, while the other iterates through the array seeking new valid elements to place.

One pointer writes, one pointer reads
Modifies the array in place
Useful for filtering without extra memory

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.

Code example

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)

void reverseArray(vector<char>& arr) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        swap(arr[left], arr[right]);
        left++;
        right--;
    }
}

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--;
    }
}

Inputarray = ['a', 'b', 'c', 'd', 'e']

Output['e', 'd', 'c', 'b', 'a']

Example

Run the example step by step

Output

Fast and slow pointers

Floyd's cycle-finding algorithm uses two pointers moving at different speeds—usually one advancing a single step and the other two steps. If there is a cycle, the fast pointer will eventually 'lap' the slow pointer and they will meet.

If the fast pointer reaches the end of the sequence, there is no cycle.

Detects cycles in linked lists
Finds the middle of a linked list in one pass
Space complexity is strictly O(1)

Managing constraints

While the logic of two pointers is elegant, edge cases require care. Ensure pointers do not cross bounds or each other incorrectly. For strings, this is the primary method for palindrome checking or reversing characters.

Always define the condition that must be met before a pointer moves, and ensure the loop terminates when the pointers meet or cross.

Check bounds (e.g., right < len)
Define loop termination (e.g., while left < right)
Handle off-by-one errors carefully