Data Structures & Algorithms Cheatsheet

Two Pointers

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

When To Reach For This

Two pointers replaces a nested loop with a single pass by moving two indices that never back up. Total work is O(n) because each pointer advances at most n times.

Signals in a problem statement:

The input is sorted, or sorting it does not destroy the answer.
You are asked for a pair, triplet, or quadruple that sums to a target.
The phrase "in place" plus "O(1) extra space".
You need to compare the array from both ends inward, as in palindromes or container problems.
Two sequences must be merged or matched in order, as in subsequence checks.
Removing or partitioning elements while preserving relative order.

Classic problems it solves:

Two Sum II, Input Array Is Sorted
3Sum and 3Sum Closest
Container With Most Water
Trapping Rain Water
Valid Palindrome
Remove Duplicates from Sorted Array
Sort Colors
Is Subsequence
Merge Sorted Array

Complexity

Variant	Time	Space	Note
opposite ends on a sorted array	O(n)	O(1)	after an O(n log n) sort if needed
fast and slow (read and write)	O(n)	O(1)	in-place compaction
two sequences merged	O(n + m)	O(1)	or O(n + m) if writing a new array
3Sum (sort plus inner two pointers)	O(n²)	O(1) extra	dominated by the outer loop
4Sum	O(n³)	O(1) extra
cycle detection (Floyd)	O(n)	O(1)	see linked lists

Opposite Ends

Start at both ends and close in. Which pointer moves is decided by comparing against the target.

def two_sum_sorted(a, target):
    i, j = 0, len(a) - 1
    while i < j:
        s = a[i] + a[j]
        if s == target:
            return [i, j]
        if s < target:
            i += 1          # need a bigger sum
        else:
            j -= 1          # need a smaller sum
    return []

def max_area(height):
    """Container With Most Water. Move the shorter wall, it limits area."""
    i, j, best = 0, len(height) - 1, 0
    while i < j:
        best = max(best, (j - i) * min(height[i], height[j]))
        if height[i] < height[j]:
            i += 1
        else:
            j -= 1
    return best

// Java: same shape, watch int overflow on sums
int i = 0, j = a.length - 1;
while (i < j) {
    long s = (long) a[i] + a[j];
    if (s == target) return new int[]{i, j};
    if (s < target) i++; else j--;
}

Fast And Slow On The Same Side

A write pointer trails a read pointer. Everything left of the write pointer is the answer so far.

def remove_duplicates(a):
    """Sorted array, keep one of each. Returns new length."""
    if not a:
        return 0
    w = 1
    for r in range(1, len(a)):
        if a[r] != a[w - 1]:
            a[w] = a[r]
            w += 1
    return w

def remove_duplicates_at_most_two(a):
    """Same, allowing each value twice. Compare against w - 2."""
    w = 0
    for x in a:
        if w < 2 or x != a[w - 2]:
            a[w] = x
            w += 1
    return w

def move_zeroes(a):
    """Push all zeroes to the end, keep the order of the rest."""
    w = 0
    for r in range(len(a)):
        if a[r] != 0:
            a[w], a[r] = a[r], a[w]
            w += 1

Fixed Outer Loop Plus Inner Two Pointers

Sorting first is what makes duplicate skipping possible. This is the 3Sum template, and the skip lines are where most submissions fail.

def three_sum(nums):
    nums.sort()
    n, res = len(nums), []
    for i in range(n - 2):
        if nums[i] > 0:
            break                   # smallest is positive, no zero sum
        if i > 0 and nums[i] == nums[i - 1]:
            continue                     # skip duplicate anchors
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1              # skip duplicate seconds
                while lo < hi and nums[hi] == nums[hi + 1]:
                    hi -= 1
    return res

Two Sequences

def is_subsequence(s, t):
    """Does s appear in t in order? O(len(t))."""
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

def merge_from_back(a, m, b, n):
    """Merge b into a in place. a has m real values then n slots."""
    i, j, w = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and a[i] > b[j]:
            a[w] = a[i]
            i -= 1
        else:
            a[w] = b[j]
            j -= 1
        w -= 1

def intersection_sorted(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return out

Choosing The Right Variant

Signal	Variant	Complexity
sorted, find a pair summing to target	opposite ends	O(n)
triplets or quadruples summing to target	sort plus inner two pointers	O(n^(k−1))
in-place filter or dedupe, keep order	read and write pointers	O(n)
compare from both ends (palindrome, area)	opposite ends	O(n)
merge or match two ordered inputs	one pointer per sequence	O(n + m)
partition into 3 groups in one pass	three pointers (Dutch flag)	O(n)
cycle in a linked list or functional graph	Floyd fast and slow	O(n)

Gotchas

while i < j versus while i <= j. For pairs you want i < j so an element is never paired with itself. For a palindrome scan i < j is also right, the middle character needs no check.
Sorting destroys original indices. If the answer requires original positions, sort (value, index) pairs or use a hash map instead.
Duplicate skipping goes after recording a hit, not before. Skipping first drops valid distinct triplets.
Move the pointer that limits the objective. In Container With Most Water that is the shorter wall, moving the taller one can never help.
The two-pointer sum trick needs monotonicity. It fails on unsorted input and on arrays where moving a pointer does not move the objective in a predictable direction.
Off-by-one on merge-from-back. Loop while j >= 0, not while both are non-negative, otherwise leftover values in b are never copied.