The two-pointer technique

Overview

What "two-pointer" really means

Imagine you have a row of boxes and you want to answer a question about them — is this word a palindrome? which pair adds up to a target? how long is the longest stretch with no repeats? The slow, obvious way is to compare every box with every other box: two nested loops, O(n^2) work. The two-pointer technique replaces that with two markers that walk the same row in a coordinated way, so the whole answer falls out in a single left-to-right (or inward) sweep — O(n).

The "pointers" can be literal C pointers (char *p) or plain array indices (size_t i). Both count as two-pointer thinking; what matters is that two positions move together under a rule you control.

This lesson builds directly on two things you already know. From Arrays, you know that array elements sit next to each other in memory and that a[i] is really *(a + i). From Pointer basics, you know how to hold an address, dereference it, and step it forward. Two-pointer is what you get when you keep two of those positions at once and give each one a job.

There are three common flavours, and almost every two-pointer problem is one of them:

• Converging — one marker starts at the left end, one at the right end, and they walk inward toward each other until they meet.
• Same-direction (slow/fast) — both markers start together and move forward, but at different speeds.
• Sliding window — both markers move forward; the region between them (the window) grows and shrinks to keep some condition true.

Why it matters

Why it matters

A huge number of "scan a sequence" problems have an obvious slow solution and a two-pointer fast solution, and the gap between them is the difference between code that finishes instantly and code that stalls on real input.

Beyond speed, two-pointer solutions are often the ones that use constant extra memory. On embedded devices, in kernels, and in tight inner loops, "O(1) extra space" is not a nicety — it is the whole reason the code is acceptable. That is why in-place reversal, in-place compaction, and cycle detection are all classic two-pointer wins.

Core concepts

There is no new syntax here — the skill is in the coordination rule each pattern uses. Study each pattern as its own tool.

Concept 1 — Converging pointers (walk inward)

Definition. Place one index i at the start and one index j at the end. At each step you compare or combine the two ends, then move i right, j left, or both. Stop when they meet or cross.

Plain language. You are pinching the sequence from both sides at once. Every step throws away one element from each end, so you finish in about n/2 steps.

How it works internally. For a palindrome, s[i] must equal s[j] for every mirrored pair. If any mirrored pair differs, it is not a palindrome and you can stop early. The loop condition i < j is what guarantees you never compare an element with itself or run past the middle.

String:  "radar"   indices 0..4

   r  a  d  a  r
   ^           ^
   i=0         j=4     s[0]=='r' == s[4]=='r'  -> advance

   r  a  d  a  r
      ^     ^
      i=1   j=3        s[1]=='a' == s[3]=='a'  -> advance

   r  a  d  a  r
         ^            i=2, j=2  ->  i < j is false, STOP: palindrome

When to use it. Sorted arrays (2-sum, closest pair), symmetry checks (palindromes), and "squeeze from both ends" problems like container-with-most-water. When NOT to: unsorted data where the order carries no meaning for your comparison, or where you must look at all pairs regardless.

Common pitfall. Using i <= j instead of i < j. With <=, when i == j you compare the middle element with itself (harmless for palindromes but wasteful) — and worse, on some formulations you step past the boundary and read out of bounds.

Knowledge check. For the string "abba" (length 4), list the exact (i, j) pairs that get compared before the loop stops. How many comparisons is that?

Concept 2 — Slow/fast pointers (different speeds)

Definition. Both pointers start at the same place and move in the same direction, but the fast one advances two steps for every one step of the slow one.

Plain language. Think of two runners on a track. If the track is a straight line, the fast runner reaches the end and it's over. If the track secretly loops, the fast runner eventually laps the slow one and they collide — that collision is your signal that a loop exists. This is Floyd's tortoise and hare.

How it works internally. Each iteration, slow moves +1 and fast moves +2, so the gap between them changes by exactly 1 per step. If there is a cycle, once both pointers are inside the loop the gap shrinks by 1 each step until it hits 0 — they must meet. A second use is finding the middle: when fast reaches the end, slow is at the halfway point.

List with a cycle (node 4 points back to node 1):

  0 -> 1 -> 2 -> 3 -> 4
       ^______________|

slow moves 1, fast moves 2 each step:

 step 1:  slow@1  fast@2
 step 2:  slow@2  fast@4
 step 3:  slow@3  fast@2   (fast wrapped through the loop)
 step 4:  slow@4  fast@4   <- MEET: cycle detected

When to use it. Linked-list cycle detection, finding the middle node in one pass, finding the start of a loop. When NOT to: random-access arrays where indices give you O(1) jumps anyway — slow/fast shines when you can only move forward one link at a time.

Common pitfall. Dereferencing without guarding. Before fast = fast->next->next, you must know both fast and fast->next are non-NULL, or you crash on the last node.

Knowledge check (find the bug). A learner writes while (fast->next) as the loop condition. On a list with an odd number of nodes and no cycle, why can this dereference NULL?

Concept 3 — Sliding window (grow and shrink)

Definition. Two indices left and right both move forward. The window is the range [left, right]. You extend right to include new elements; when a rule (the invariant) breaks, you advance left to shrink the window until the rule holds again.

Plain language. Picture a stretchy frame sliding along the sequence. You grow it greedily; the moment it becomes "illegal," you pull the trailing edge forward until it's legal again. Because each pointer only ever moves forward, the total work is O(n) even though the window itself moves back and forth in size.

How it works internally. For "longest substring without repeating characters," the invariant is "every character in the window is distinct." You typically keep a small lookup (e.g. a 256-entry seen[] table for ASCII) recording where each character last appeared, so you can jump left past the previous duplicate in O(1).

s = "abcabcbb"

[a]bcabcbb        window "a"     len 1
[ab]cabcbb        window "ab"    len 2
[abc]abcbb        window "abc"   len 3  <- best so far
a[bca]bcbb        'a' repeats -> shrink left past old 'a'
ab[cab]cbb        'b' repeats -> shrink
...
best length = 3

When to use it. Longest/shortest contiguous run satisfying a property, running sums, throttling and rate windows in logs. When NOT to: problems where the answer is not a contiguous range, or where shrinking from the left can never restore the invariant.

Common pitfall. Moving left by only 1 when a duplicate is found deep in the window, instead of jumping it past the duplicate's last position — that can silently keep an illegal character inside the window.

Knowledge check (explain in your own words). Why is a sliding window O(n) even though left and right together seem to "revisit" elements? (Hint: count how many times each pointer can move.)

Choosing a pattern

Syntax notes

There is no special language feature — you declare two positions and a loop. What varies is the movement rule.

/* Converging: start at both ends, walk inward */
size_t i = 0, j = len;          /* j is one PAST the last valid index */
while (i < j) {                 /* strict < : stop when they meet */
    /* compare s[i] with s[j-1], then: */
    i++;
    j--;
}

/* Slow/fast on a linked list */
node_t *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL) {  /* guard BOTH before ->next->next */
    slow = slow->next;          /* +1 */
    fast = fast->next->next;    /* +2 */
}

/* Sliding window over a string */
size_t left = 0;
for (size_t right = 0; s[right] != '\0'; right++) {
    /* extend window to include s[right]; if invariant broke, advance left */
}

Use size_t for indices into arrays and strings — it is unsigned and matches what strlen returns, avoiding signed/unsigned comparison warnings.

Lesson

Two-pointer is a family of algorithms. In all of them, two indices walk a structure at coordinated speeds.

Examples:

• Palindrome check — converge from both ends.
• Cycle detection (Floyd) — slow and fast pointers.
• Sliding-window substring problems — a window that grows and shrinks.

Code examples

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Converging two-pointer: is the whole string a palindrome? O(n), O(1) space. */
int is_palindrome(const char *s) {
    size_t i = 0;
    size_t j = strlen(s);            /* j = length; treat it as one-past-the-end */
    while (i < j) {
        j--;                         /* step j to a valid index before reading */
        if (s[i] != s[j]) return 0;  /* mismatched mirror pair -> not a palindrome */
        i++;
    }
    return 1;                        /* all mirror pairs matched (empty string counts) */
}

/* Sliding-window two-pointer: length of the longest substring with no repeats.
   Assumes ASCII input. O(n) time, O(1) extra space (fixed 256-entry table). */
int longest_unique(const char *s) {
    int last_seen[256];              /* last_seen[c] = index+1 of last occurrence, 0 = never */
    for (int c = 0; c < 256; c++) last_seen[c] = 0;

    int best = 0;
    size_t left = 0;                 /* window start */
    for (size_t right = 0; s[right] != '\0'; right++) {
        unsigned char c = (unsigned char)s[right];
        if (last_seen[c] > (int)left) /* c already inside the current window? */
            left = (size_t)last_seen[c];   /* jump left past the duplicate */
        last_seen[c] = (int)right + 1;     /* record 1-based position of c */
        int window_len = (int)(right - left + 1);
        if (window_len > best) best = window_len;
    }
    return best;
}

int main(void) {
    const char *tests[] = { "radar", "hello", "abba", "", "x" };
    size_t n = sizeof(tests) / sizeof(tests[0]);
    for (size_t k = 0; k < n; k++)
        printf("is_palindrome(\"%s\") = %d\n", tests[k], is_palindrome(tests[k]));

    const char *words[] = { "abcabcbb", "bbbbb", "pwwkew", "abcdef" };
    size_t m = sizeof(words) / sizeof(words[0]);
    for (size_t k = 0; k < m; k++)
        printf("longest_unique(\"%s\") = %d\n", words[k], longest_unique(words[k]));
    return 0;
}

What it does. The program exercises two of the three patterns. is_palindrome converges from both ends; longest_unique slides a window and uses a 256-entry table to jump past duplicates.

Expected output:

is_palindrome("radar") = 1
is_palindrome("hello") = 0
is_palindrome("abba") = 1
is_palindrome("") = 1
is_palindrome("x") = 1
longest_unique("abcabcbb") = 3
longest_unique("bbbbb") = 1
longest_unique("pwwkew") = 3
longest_unique("abcdef") = 6

Edge cases. The empty string is a palindrome (the loop body never runs). A single character is trivially a palindrome and has longest-unique length 1. Casting to unsigned char before indexing last_seen matters: on platforms where char is signed, a byte like 0xC3 would otherwise become a negative index and read out of bounds.

Line by line

Tracing is_palindrome("abba") (length 4):

Return 1. Notice j starts as the length (4, one past the last index) and is decremented to a valid index inside the loop before any read — that is the guard against reading s[4].

Tracing longest_unique("pwwkew"):

At right=2 the second w is inside the window, so left jumps to 2 (past the first w). The window "wke" at right=4 gives length 3, the answer. The > left test (not >= 0) is what stops stale positions outside the window from wrongly shrinking it.

The slow/fast walkthrough from the original lesson, guarded correctly:

node_t *slow = head, *fast = head;
while (fast && fast->next) {   /* both non-NULL, so ->next->next is safe */
    slow = slow->next;         /* tortoise: +1 */
    fast = fast->next->next;   /* hare: +2 */
    if (slow == fast) return 1;/* they collided -> a cycle exists */
}
return 0;                      /* fast ran off the end -> no cycle */

Each iteration the tortoise gains one link and the hare gains two, so inside a loop the hare closes the gap by exactly one per step and a meeting is guaranteed. If the list is straight, fast or fast->next becomes NULL and the loop exits cleanly.

Common mistakes

Mistake 1 — Reading before you validate the index.

/* WRONG: reads s[strlen(s)], one past the terminator */
size_t i = 0, j = strlen(s);
while (i < j) {
    if (s[i] != s[j]) return 0;   /* first iteration reads s[len] */
    i++; j--;
}

On the first pass j equals the length, so s[j] reads the byte after the string. Fix: decrement j before the read (j--; if (s[i] != s[j]) ...) or initialise j = strlen(s) - 1 and use while (i < j) — but beware strlen of "" is 0, so 0 - 1 underflows size_t to a huge number. The j = len then j-- inside the loop form avoids that trap.

Mistake 2 — Unguarded fast pointer.

/* WRONG: crashes at the end of an odd-length list */
while (fast->next) {
    fast = fast->next->next;   /* if fast->next is the last node, ->next is NULL, ->next->next crashes */
    slow = slow->next;
}

Fix: check fast && fast->next before the double step. Recognise it: a segfault that only happens on some list lengths (odd vs even) is the fingerprint of a missing NULL guard.

Mistake 3 — Shrinking the window by one instead of jumping.

/* WRONG: only moves left by 1, may leave the duplicate inside */
if (seen_in_window(c)) left++;

If the duplicate is several positions inside the window, a single left++ still leaves it there and the invariant stays broken. Fix: jump left to just past the duplicate's last index. Prevent it: always ask "after this move, is the invariant guaranteed restored, not just nudged toward restoration?"

Mistake 4 — i <= j on a converging loop. With <=, at i == j you compare an element with itself and, in strlen-1 formulations, can step j below 0. Use strict <.

Debugging tips

Compiler warnings to fix first. Turn on -Wall -Wextra. The classic here is "comparison of integer expressions of different signedness" — it means you mixed a signed int index with the unsigned size_t from strlen. Make both size_t, or cast deliberately.

Runtime crashes. A segfault in linked-list code almost always means an unguarded ->next. Run under a sanitizer:

cc -fsanitize=address,undefined -g two_pointer.c && ./a.out

AddressSanitizer pinpoints the exact out-of-bounds read (e.g. s[len]) and UBSan flags the signed/unsigned underflow.

Logic errors. When the answer is wrong but nothing crashes, print both pointers every iteration:

printf("i=%zu j=%zu s[i]=%c s[j]=%c\n", i, j, s[i], s[j]);

Questions to ask when it doesn't work:

• Does the loop stop when the pointers meet, or does it run one step too far?
• On the very first iteration, is every index I read actually in bounds?
• For slow/fast: did I check fast && fast->next before both ->next steps?
• For the window: after I move left, is the invariant truly restored, or only partly?
• Off-by-one bugs cluster at the meet point — trace the last two iterations by hand.

Memory safety

Two-pointer code lives or dies on staying in bounds and guarding lifetimes, because pointer arithmetic here is deliberately walking to the edges of a structure.

• Bounds. The valid indices of an n-element array are 0 .. n-1. A converging loop must never read a[n]. The safe idiom is j = len; then j-- before each read, so j is always a legal index at the moment of dereference.
• size_t underflow. size_t is unsigned, so 0 - 1 wraps to SIZE_MAX, not -1. Never write j = strlen(s) - 1 without first proving the string is non-empty. This is a real undefined-behaviour trap that turns into a wild out-of-bounds read.
• NULL dereference (linked lists). Before fast->next->next, both fast and fast->next must be non-NULL. The guard while (fast && fast->next) is not optional — it is the memory-safety contract of the pattern.
• Signed char indexing. When a byte indexes a lookup table (last_seen[s[right]]), cast through unsigned char. A signed char holding 0x80..0xFF becomes negative and indexes before the array — a silent out-of-bounds read.
• Initialisation. The window's lookup table must be zeroed before use; reading an uninitialised last_seen[] entry is undefined behaviour and produces garbage window boundaries.
• Ownership. Two-pointer scans typically read a caller-owned buffer. Take const char * when you only read, so the compiler stops you from accidentally writing through it, and never free a buffer you did not allocate.

Real-world uses

Concrete uses. In-place memmove-style compaction in libraries; strrev/palindrome checks in text tools; two-pointer merge in merge-sort and in database join engines over sorted runs; Floyd's cycle detection in garbage collectors and in linked-structure validators; sliding windows in rate limiters, TCP flow-control windows, and log-analysis tools that ask "most events of one type within any 60-second span." Defensive scanners (log filters, simple pattern matchers) use the same coordinated-index skeleton.

Professional habits — beginner.

• Name pointers for their role: left/right, slow/fast, not p1/p2.
• Pick the loop bound (< vs <=) deliberately and write a one-line comment saying why it stops there.
• Use const on read-only inputs; use size_t for indices.
• Validate inputs (NULL string? empty list?) before entering the loop.

Professional habits — advanced.

• State the invariant in a comment above the window loop, then check every branch preserves it.
• Prove the O(n) bound by arguing each pointer moves forward at most n times.
• Prefer O(1)-extra-space two-pointer forms where memory is constrained (embedded, kernel, hot loops).
• Fuzz the routine (empty, length 1, all-same, no-repeats, cycle at head/tail) and run it under ASan/UBSan in CI.

Practice tasks

1. (Beginner) Reverse an array in place. Implement void reverse_array(int *a, size_t n) that reverses the first n elements using converging indices — no second array. Requirements: swap a[i] and a[j], move inward, stop at the middle. Example: {1,2,3,4,5} becomes {5,4,3,2,1}. Constraint: O(1) extra space. Hint: loop while i < j. Concept: converging.

2. (Beginner) Palindrome check. Implement int is_palindrome(const char *s) returning 1/0 for the whole string. Requirements: handle "" (return 1) and single characters. Example: "level" -> 1, "open" -> 0. Hint: start j = strlen(s) and decrement before reading. Concept: converging.

3. (Intermediate) Find the middle node. Implement node_t *list_middle(node_t *head) returning the middle node in a single pass; for even length return the second of the two middle nodes. Requirements: one traversal, O(1) space, no length counting. Hint: when fast reaches the end, slow is at the middle. Concept: slow/fast.

4. (Intermediate) Longest substring without repeats. Implement int longest_unique(const char *s) for ASCII input. Example: "abcabcbb" -> 3, "bbbbb" -> 1. Requirements: single pass, O(1) extra space via a fixed table; cast bytes through unsigned char. Hint: jump left past a duplicate, do not step by 1. Concept: sliding window.

5. (Challenge) Detect a cycle and return its length. Implement int cycle_length(node_t *head) that returns 0 if the list has no cycle, otherwise the number of nodes in the cycle. Requirements: use Floyd's slow/fast to detect a meeting point, then keep one pointer fixed and advance the other around the loop to count nodes. Constraint: O(1) extra space, and never dereference NULL. Hint: after the pointers meet inside the loop, one more lap measures its length. Concepts: slow/fast, then a counting walk.

Summary

• One structure, two coordinated positions. Give each pointer a job and a movement rule, and many O(n^2) scans collapse to a single O(n) pass — often with O(1) extra memory.
• Three patterns. Converging (walk inward from both ends: palindromes, sorted 2-sum), slow/fast (different speeds: cycle detection, middle node), sliding window (grow/shrink to hold an invariant: longest-unique-substring).
• Key syntax. Two indices (size_t) or two pointers and a loop; the movement rule lives in the loop body, and the stop condition (i < j, or fast && fast->next) is load-bearing.
• Common mistakes. Reading before validating an index, unguarded fast->next->next, size_t underflow from strlen("") - 1, signed-char table indexing, and nudging the window by 1 instead of jumping past a duplicate.
• Remember: off-by-one bugs cluster at the meet point — trace the last two iterations by hand, and turn on -Wall -Wextra -fsanitize=address,undefined to catch bounds and signedness bugs early.

Practice with these exercises

• Reverse an array in place
• Palindrome check
• Case-insensitive alphanumeric palindrome check
• Reverse words of a sentence in place
• Detect a cycle in a linked list
• Longest substring without repeating characters
• Find the middle node of a singly linked list