👉 Two Pointers

The night-before sheet: spot the pattern, write it the way you already wrote it, say why it's safe.

💭 There's no Two Pointers group in your DSA thoughts yet. The related ones (Arrays #1, #2, Math #3, JS #1) are linked where they apply.

🧠 0 · How to think

"Two fingers on the data instead of two loops. Each finger only moves forward, so the whole thing is one pass."

The skill is the move rule: which finger moves, and why moving it can never skip an answer. Once you can say that in one sentence, the code is a few lines.

🧭 1 · Spot it

🚶 2 · Converging: both ends, move inward

"Squeeze from both ends; drop the one that can't help."

167 · Two Sum II (the template) ⏱️ O(n) · 📦 O(1)

💡 Sum too big → j--. Too small → i++. Equal → done.

function twoSum(nums: number[], target: number): number[] {
    let i = 0;
    let j = nums.length - 1;

    while(i < j) {
        const sum = nums[i] + nums[j];

        if(sum > target) j--;        // too big → only j can make it smaller
        else if(sum < target) i++;   // too small → only i can make it bigger
        else return [i + 1, j + 1];
    }

    return [];
};

11 · Container With Most Water ⏱️ O(n) · 📦 O(1)

💡 Area = shorter wall × width. Move the shorter wall: it caps the water, so keeping it can only give less.

function maxArea(height: number[]): number {
    let i = 0;
    let j = height.length - 1;
    let maxArea = 0;

    while(i < j) {
        const minHei = Math.min(height[i], height[j]);
        const width = j - i;
        maxArea = Math.max(maxArea, minHei * width);

        // move the SHORTER wall: it caps the water, and moving the taller one can't help
        if(height[i] < height[j]) i++;
        else j--;
    }

    return maxArea;
};

42 · Trapping Rain Water ⏱️ O(n) · 📦 O(1)

💡 Water above a bar = min(leftMax, rightMax) − height. Move the side with the smaller max: that max is the bottleneck, so its water is already known.

function trap(height: number[]): number {
    const n = height.length;
    let left = 0;
    let right = n - 1;
    let leftMaxHei = height[0];
    let rightMaxHei = height[n - 1];
    let res = 0;

    while(left < right) {
        // the side with the smaller max is the bottleneck, so its water is known
        if(leftMaxHei < rightMaxHei) {
            left++;
            leftMaxHei = Math.max(leftMaxHei, height[left]);
            res += leftMaxHei - height[left];
        } else {
            right--;
            rightMaxHei = Math.max(rightMaxHei, height[right]);
            res += rightMaxHei - height[right];
        }
    }

    return res;
};

680 · Valid Palindrome II ⏱️ O(n) · 📦 O(1)

💡 Normal palindrome check. On the first mismatch you get one delete: try skipping the left char or the right char.

function validPalindrome(s: string): boolean {
    function isPalin(i: number, j: number): boolean {
        while(i < j) {
            if(s[i] !== s[j]) return false;
            i++;
            j--;
        }
        return true;
    }

    let i = 0;
    let j = s.length - 1;

    while(i < j) {
        if(s[i] !== s[j]) {
            // one delete allowed: skip the left char OR the right char
            return isPalin(i + 1, j) || isPalin(i, j - 1);
        }
        i++;
        j--;
    }

    return true;
};

977 · Squares of a Sorted Array ⏱️ O(n) · 📦 O(n) output

💡 Negatives make the biggest square sit at one of the two ends. Compare the ends and fill the result from the back.

function sortedSquares(nums: number[]): number[] {
    const n = nums.length;
    const res: number[] = Array(n).fill(0);
    let i = 0;
    let j = n - 1;
    let k = n - 1;              // fill from the BACK: the biggest square is at an end

    while(i < j) {
        const sq1 = nums[i] ** 2;
        const sq2 = nums[j] ** 2;

        if(sq1 <= sq2) {
            res[k--] = sq2;
            j--;
        } else {
            res[k--] = sq1;
            i++;
        }
    }

    res[0] = nums[i] ** 2;      // i === j: the last one is the smallest
    return res;
};

881 · Boats to Save People ⏱️ O(n log n) · 📦 O(n) sorted copy

💡 Sort. The heaviest always leaves now; take the lightest along if they fit together.

function numRescueBoats(people: number[], limit: number): number {
    const sorted = [...people].sort((a, b) => b - a);   // heaviest first
    let boats = 0;
    let i = 0;                  // heaviest left
    let j = sorted.length - 1;  // lightest left

    while(i < j) {
        if(sorted[i] + sorted[j] <= limit) j--;   // lightest fits with the heaviest
        boats++;                                  // the heaviest always leaves
        i++;
    }

    if(i === j) boats++;        // one person left over
    return boats;
};

📌 3 · k-Sum: fix one, then 2Sum the rest

"3Sum = a for-loop around 2Sum."

15 · 3Sum ⏱️ O(n²) · 📦 O(n) sorted copy

💡 Sort. For each i, run the 167 squeeze on the right part. Skip equal values (for i, and for left/right after a hit) so no triplet repeats.

function threeSum(nums: number[]): number[][] {
    const n = nums.length;
    const sorted = [...nums].sort((a, b) => a - b);
    const res: number[][] = [];

    for(let i = 0; i < n; i++) {
        // same value as before → its triplets are already found
        if(i > 0 && sorted[i] === sorted[i - 1]) continue;

        let left = i + 1;
        let right = n - 1;

        while(left < right) {
            const sum = sorted[i] + sorted[left] + sorted[right];

            if(sum < 0) {
                left++;
            } else if(sum > 0) {
                right--;
            } else {
                res.push([sorted[i], sorted[left], sorted[right]]);

                while(left < right && sorted[left] === sorted[left + 1]) left++;
                while(left < right && sorted[right] === sorted[right - 1]) right--;

                left++;
                right--;
            }
        }
    }

    return res;
};

🐢🐇 4 · Fast & Slow: linked lists

"Slow moves 1, fast moves 2. If there's a loop, the hare laps the tortoise."

141 · Linked List Cycle ⏱️ O(n) · 📦 O(1)

💡 while(fast && fast.next); meet → cycle, fast hits null → no cycle.

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;

    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;

        if(slow === fast) return true;
    }

    return false;
};

142 · Linked List Cycle II (where does it start?) ⏱️ O(n) · 📦 O(1)

💡 After they meet, send one pointer back to head; move both 1 step at a time; they meet at the cycle start.

Why: head → start is the same distance as meeting point → start (going round the loop). So two walkers at speed 1 arrive together.

function detectCycle(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if(slow === fast) {
            fast = head;                 // restart one from head, both at speed 1
            while(slow !== fast) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;                 // they meet at the cycle start
        }
    }

    return null;
};

876 · Middle of the Linked List ⏱️ O(n) · 📦 O(1)

💡 When fast reaches the end, slow is in the middle.

function middleNode(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;    // even length → the SECOND middle
};

160 · Intersection of Two Linked Lists ⏱️ O(m + n) · 📦 O(1)

💡 When a pointer runs off its list, jump it to the other list’s head. Both walk A + B, so they meet at the join, or both reach null.

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let l1 = headA;
    let l2 = headB;

    // each walks A + B; same total length, so they line up at the join (or both hit null)
    while(l1 !== l2) {
        l1 = l1 ? l1.next : headB;
        l2 = l2 ? l2.next : headA;
    }

    return l1;
};

234 · Palindrome Linked List ⏱️ O(n) · 📦 O(1)

💡 Middle → reverse the second half → compare the halves node by node.

function isPalindrome(head: ListNode | null): boolean {
    // 1 find the middle
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2 reverse from the middle to the end
    let prev = null;
    let curr = slow;
    while(curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    // 3 compare the two halves
    let first = head;
    let second = prev;
    while(first && second) {
        if(first.val !== second.val) return false;
        first = first.next;
        second = second.next;
    }

    return true;
};

143 · Reorder List ⏱️ O(n) · 📦 O(1)

💡 Middle → cut and reverse the second half → zip: one from the front, one from the back.

function reorderList(head: ListNode | null): void {
    if(head === null || head.next === null) return;

    // 1 find the middle
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2 reverse from mid to end (and cut the list in two)
    let prev = null;
    let curr = slow.next;
    slow.next = null;
    while(curr) {
        const nextNode = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextNode;
    }

    // 3 zip the two halves
    let first = head;
    let second = prev;
    while(second !== null) {
        const firstNext = first.next;
        const secondNext = second.next;
        first.next = second;
        second.next = firstNext;
        first = firstNext;
        second = secondNext;
    }
};

19 · Remove Nth Node From End ⏱️ O(n) · 📦 O(1)

💡 Your version: count the length, then stop on the node before the one to delete. len === n means delete the head.

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let len = 0;
    let curr = head;
    while(curr) {
        len++;
        curr = curr.next;
    }

    if(len === n) return head.next;      // removing the head itself

    let steps = len - n - 1;             // stop on the node BEFORE the one to delete
    curr = head;
    while(steps--) curr = curr.next;

    curr.next = curr.next.next;
    return head;
};

📚 5 · Write pointer: same direction, in place

"Read scans everything; write marks where the next keeper goes. Everything left of write is done."

283 · Move Zeroes ⏱️ O(n) · 📦 O(1)

💡 Non-zero → swap it to write, write++. Zeroes end up at the back, order kept.

function moveZeroes(nums: number[]): void {
    let write = 0;

    for(let read = 0; read < nums.length; read++) {
        if(nums[read] !== 0) {
            [nums[read], nums[write]] = [nums[write], nums[read]];
            write++;
        }
    }
};

26 · Remove Duplicates from Sorted Array ⏱️ O(n) · 📦 O(1)

💡 Keep a value if it differs from the last kept one (nums[write - 1]). Return write, the count.

80 (keep at most 2): compare with nums[write - 2] instead.

function removeDuplicates(nums: number[]): number {
    let write = 1;   // the next slot to fill; nums[0] is always kept

    for(let read = 1; read < nums.length; read++) {
        if(nums[read] !== nums[write - 1]) {
            [nums[read], nums[write]] = [nums[write], nums[read]];
            write++;
        }
    }

    return write;
};

🔀 Two arrays, one pointer each

🔀 One finger on each array, like merging two sorted piles of cards: compare the two top cards, take one, move only that finger.

Two sorted inputs, a pointer in each, move the one that's behind. This is the merge step of merge sort.

88 · Merge Sorted Array ⏱️ O(m + n) · 📦 O(1)

💡 Fill nums1 from the back: those slots are empty, so nothing gets overwritten. Leftover nums1 is already in place.

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let i = m - 1;
    let j = n - 1;
    let k = m + n - 1;     // fill from the BACK: those slots are empty, nothing gets overwritten

    while(i >= 0 && j >= 0) {
        if(nums1[i] >= nums2[j]) nums1[k--] = nums1[i--];
        else nums1[k--] = nums2[j--];
    }

    while(j >= 0) nums1[k--] = nums2[j--];   // leftover nums1 is already in place
};

392 · Is Subsequence ⏱️ O(n) · 📦 O(1)

💡 Walk t; move s’s pointer only on a match. All of s matched → true.

function isSubsequence(s: string, t: string): boolean {
    let sIdx = 0;

    for(let tIdx = 0; tIdx < t.length && sIdx < s.length; tIdx++) {
        if(t[tIdx] !== s[sIdx]) continue;
        sIdx++;
    }

    return sIdx === s.length;
};

350 · Intersection of Two Arrays II ⏱️ O(m log m + n log n) · 📦 O(m + n)

💡 Sort both. Smaller value moves; equal → take it and move both.

function intersect(nums1: number[], nums2: number[]): number[] {
    const sorted1 = [...nums1].sort((a, b) => a - b);
    const sorted2 = [...nums2].sort((a, b) => a - b);
    const res: number[] = [];
    let i = 0;
    let j = 0;

    while(i < sorted1.length && j < sorted2.length) {
        if(sorted1[i] < sorted2[j]) i++;
        else if(sorted1[i] > sorted2[j]) j++;
        else {
            res.push(sorted1[i]);    // match → take it, move BOTH
            i++;
            j++;
        }
    }

    return res;
};

844 · Backspace String Compare ⏱️ O(m + n) · 📦 O(1)

💡 Walk both strings from the end, skipping chars erased by #; compare the survivors one by one.

function backspaceCompare(s: string, t: string): boolean {
    let i = s.length - 1;
    let j = t.length - 1;

    // walk back to the next char that survives the backspaces
    function nextValid(s: string, idx: number): number {
        let backspace = 0;
        while(idx >= 0) {
            if(s[idx] === '#') backspace++;
            else if(backspace > 0) backspace--;
            else return idx;
            idx--;
        }
        return idx;
    }

    while(i >= 0 || j >= 0) {
        i = nextValid(s, i);
        j = nextValid(t, j);

        if(i < 0 && j < 0) return true;
        if(i < 0 || j < 0) return false;
        if(s[i] !== t[j]) return false;

        i--;
        j--;
    }

    return true;
};

🗑️ 6 · Three-way partition

"Three bins: 0s go left, 2s go right, 1s stay in the middle."

75 · Sort Colors (Dutch flag) ⏱️ O(n) · 📦 O(1)

💡 0 → swap left, move left and mid. 1 → mid++. 2 → swap right, right-- and don’t move mid.

function sortColors(nums: number[]): void {
    let left = 0;               // next slot for a 0
    let mid = 0;                // the scanner
    let right = nums.length - 1; // next slot for a 2

    while(mid <= right) {
        if(nums[mid] === 0) {
            [nums[left], nums[mid]] = [nums[mid], nums[left]];
            left++;
            mid++;              // what came from left is already checked (a 0 or a 1)
        } else if(nums[mid] === 1) {
            mid++;
        } else {
            [nums[right], nums[mid]] = [nums[mid], nums[right]];
            right--;            // NO mid++: the value from the right is unchecked
        }
    }
};

2161 Partition Around a Pivot keeps the original order, so it's a stable 3-pass (less, equal, greater) rather than swaps.

🧰 7 · Array tricks (in the tracker next to two pointers)

Not really two-pointer patterns, but asked in the same rounds. Know the one line.

189 · Rotate Array ⏱️ O(n) · 📦 O(1)

💡 k %= n, then reverse all, reverse the first k, reverse the rest.

function rotate(nums: number[], k: number): void {
    const n = nums.length;
    k = k % n;

    function reverse(start: number, end: number) {
        while(start < end) {
            [nums[start], nums[end]] = [nums[end], nums[start]];
            start++;
            end--;
        }
    }

    reverse(0, n - 1);   // [1..7] → [7..1]
    reverse(0, k - 1);   // first k back in order
    reverse(k, n - 1);   // the rest back in order
};

31 · Next Permutation ⏱️ O(n) · 📦 O(1)

💡 Find the pivot from the right (first nums[i] < nums[i + 1]), swap it with the rightmost bigger value, reverse the suffix.

function nextPermutation(nums: number[]): void {
    const n = nums.length;

    function reverse(s: number, e: number): void {
        while(s < e) {
            [nums[s], nums[e]] = [nums[e], nums[s]];
            s++;
            e--;
        }
    }

    // 1 pivot: first nums[i] < nums[i + 1] from the right
    let pivot = -1;
    for(let i = n - 2; i >= 0; i--) {
        if(nums[i] < nums[i + 1]) {
            pivot = i;
            break;
        }
    }

    if(pivot === -1) {        // fully descending → wrap to the smallest
        reverse(0, n - 1);
        return;
    }

    // 2 swap with the rightmost value bigger than the pivot
    for(let i = n - 1; i > pivot; i--) {
        if(nums[pivot] < nums[i]) {
            [nums[pivot], nums[i]] = [nums[i], nums[pivot]];
            break;
        }
    }

    // 3 the suffix is descending → reverse it to make it the smallest
    reverse(pivot + 1, n - 1);
};

238 · Product of Array Except Self ⏱️ O(n) · 📦 O(n) suffix array

💡 Left pass stores the product of everything to the left; right pass multiplies in everything to the right. No division.

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const suffix = Array(n + 1).fill(1);
    const ans = Array(n).fill(1);

    // ans[i] = product of everything LEFT of i
    for(let i = 1; i < n; i++) {
        ans[i] = ans[i - 1] * nums[i - 1];
    }

    // × product of everything RIGHT of i
    for(let i = n - 1; i >= 0; i--) {
        suffix[i] = suffix[i + 1] * nums[i];
        ans[i] = ans[i] * suffix[i + 1];
    }

    return ans;
};

⭐ 8 · Must-know, one line each

If you can say the trick for each in one sentence, you're ready.

⚠️ 9 · Traps, and the input that shows each one

Complexity

Why it's linear: each pointer only moves forward and never resets, so total work ≤ total distance the pointers can travel.

✅ 10 · Self-check

Cover the right column (it's blurred; hover or tap to reveal). Say the answer out loud first.

Write these cold (no peeking)

• Converging 167, 11, 42
• k-Sum 15
• Fast & Slow 141, 142, 143
• Write pointer 283, 26, 88
• Three-way 75

The code on this page is your own accepted LeetCode code, trimmed (brute-force blocks, header comments and edge cases the constraints rule out are removed) and re-tested on the LeetCode examples.