Two Pointers | Phase 4

Three Variants

Opposite ends

lo=0, hi=n-1. Move towards center. Used on sorted arrays. Problems: two sum sorted, container water, palindrome check.

Same direction

slow=0, fast=0. Fast advances first. Used for: remove duplicates, move zeros, partition arrays.

Two arrays

i=0, j=0. Each points into a different array. Used for: merge sorted arrays, compare versions, intersection.

Pattern Templates

C++
// OPPOSITE ENDS — typical on sorted array
int lo=0, hi=n-1;
while(lo < hi) {
    if(condition) lo++;       // need larger left
    else if(other) hi--;      // need smaller right
    else {/*found*/; lo++; hi--;} // process match
}

// FAST/SLOW (same direction) — remove in-place
int slow=0;
for(int fast=0; fast<n; fast++) {
    if(valid(nums[fast])) {
        nums[slow++] = nums[fast];  // compact valid elements
    }
}
// After loop: nums[0..slow-1] has valid elements
    

Interactive: Two Sum II — Opposite Ends

Sorted array [1,2,7,11,15], target=9. Two pointers squeeze inward — sum too large means move hi left, sum too small means move lo right.

Practice Problems

#167Two Sum II — Input Array Is SortedMedium

Find two numbers in sorted array that add to target. Return 1-indexed positions.

Pattern: Opposite ends. Sum too small → move lo right (increase sum). Sum too large → move hi left (decrease sum).

C++
vector<int> twoSum(vector<int>& nums, int target) {
    int lo=0, hi=nums.size()-1;
    while(lo<hi) {
        int s=nums[lo]+nums[hi];
        if     (s==target) return {lo+1,hi+1};
        else if(s<target)  lo++;
        else               hi--;
    }
    return {};
}
// Time: O(n)  Space: O(1)

#153SumMedium

Find all unique triplets that sum to zero.

Pattern: Sort + fix one element + two-pointer on the rest. Skip duplicates carefully at both the outer loop and inner pointers.

C++
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    vector<vector<int>> res;
    for(int i=0;i<nums.size()-2;i++) {
        if(i>0&&nums[i]==nums[i-1]) continue;  // skip dup
        int lo=i+1, hi=nums.size()-1;
        while(lo<hi) {
            int s=nums[i]+nums[lo]+nums[hi];
            if(s==0) {
                res.push_back({nums[i],nums[lo],nums[hi]});
                while(lo<hi&&nums[lo]==nums[lo+1]) lo++;
                while(lo<hi&&nums[hi]==nums[hi-1]) hi--;
                lo++; hi--;
            } else if(s<0) lo++;
            else hi--;
        }
    }
    return res;
}
// Time: O(n²)  Space: O(1)

#42Trapping Rain WaterHard

Given elevation map, compute water it can trap after rain.

Pattern: Two pointers. At each step, process the side with smaller max height. Water at position = min(maxLeft, maxRight) - height.

C++
int trap(vector<int>& h) {
    int lo=0, hi=h.size()-1, maxL=0, maxR=0, water=0;
    while(lo<hi) {
        if(h[lo]<h[hi]) {
            h[lo]>=maxL ? maxL=h[lo] : water+=maxL-h[lo];
            lo++;
        } else {
            h[hi]>=maxR ? maxR=h[hi] : water+=maxR-h[hi];
            hi--;
        }
    }
    return water;
}
// Time: O(n)  Space: O(1)

#125Valid PalindromeEasy

Given a string, return true if it is a palindrome considering only alphanumeric characters, ignoring case.

Pattern: Opposite ends on a string. Skip non-alphanumeric characters from both sides, compare lowercased characters, move inward.

C++
bool isPalindrome(string s) {
    int lo=0, hi=s.size()-1;
    while(lo<hi) {
        while(lo<hi && !isalnum(s[lo])) lo++;
        while(lo<hi && !isalnum(s[hi])) hi--;
        if(tolower(s[lo])!=tolower(s[hi])) return false;
        lo++; hi--;
    }
    return true;
}
// Time: O(n)  Space: O(1)

#75Sort ColorsMedium

Sort an array of 0s, 1s and 2s in-place in one pass (Dutch National Flag).

Pattern: Three pointers — lo (next 0 slot), hi (next 2 slot), mid (scanner). Swap 0s to the front, 2s to the back. After swapping a 2 in, do NOT advance mid — the swapped value is unexamined.

C++
void sortColors(vector<int>& nums) {
    int lo=0, mid=0, hi=nums.size()-1;
    while(mid<=hi) {
        if     (nums[mid]==0) swap(nums[lo++],nums[mid++]);
        else if(nums[mid]==2) swap(nums[mid],nums[hi--]);  // mid stays!
        else                   mid++;
    }
}
// Time: O(n)  Space: O(1) — single pass

#26Remove Duplicates from Sorted ArrayEasy

Remove duplicates in-place from sorted array. Return new length. Do not allocate extra space.

Pattern: Slow/fast pointers. Fast scans, slow writes unique elements.

C++
int removeDuplicates(vector<int>& nums) {
    int slow=1;
    for(int fast=1;fast<nums.size();fast++)
        if(nums[fast]!=nums[fast-1])
            nums[slow++]=nums[fast];
    return slow;
}
// Time: O(n)  Space: O(1)

#11Container With Most WaterMedium

Find two lines that together with x-axis form a container holding most water.

Pattern: Start with widest container (lo=0, hi=n-1). Move the shorter line inward — only this can possibly find a larger area.

C++
int maxArea(vector<int>& h) {
    int lo=0, hi=h.size()-1, res=0;
    while(lo<hi) {
        res=max(res, min(h[lo],h[hi])*(hi-lo));
        h[lo]<h[hi] ? lo++ : hi--;
    }
    return res;
}
// Time: O(n)  Space: O(1)

When to use Two Pointers: Sorted array or string. "Find pair that sums to X". "Remove elements in-place". "Reverse / palindrome check". "Minimize/maximize some quantity with a constraint on two ends."

Deeper Understanding

🧠 Under the Hood — why O(n²) collapses to O(n)

Every comparison either moves lo right or hi left, and sorted order guarantees the discarded pairs could never be the answer. If the sum is too small, no pair using this lo works (hi is already the largest partner available) — so an entire row of the candidate grid is eliminated in O(1). The pointers can move at most n−1 times combined, which is the whole complexity proof.

⚖️ When to Use / When NOT to Use

✅ Use when the array is sorted (or you can sort it) and you need a pair/triplet meeting a condition

Sorted order is what makes discarding provably safe — sum too small means lo's partner can't exist.

✅ Use when you need in-place compaction or partitioning (remove/move elements, Dutch flag)

Slow/fast pointers write and read in one pass with O(1) extra space.

❌ Avoid when the array is unsorted and order must be preserved (can't sort)

Instead: hash map — Two Sum on unsorted input is the classic hash-map problem.

❌ Avoid when you need the original indices after sorting

Instead: sort pairs of (value, index), or use a hash map that stores indices directly.

🚫 Common Misconceptions

"Two pointers works on any array"

It needs a monotonic structure — sorted values, a partition invariant, or a shrinking window whose validity is monotone. On arbitrary unsorted data the discard step is unsound.

"Moving the pointer might skip the answer"

The proof is the point: in Container With Most Water, moving the taller line can only shrink area, so skipping it is safe. If you can't argue this, two pointers is the wrong tool.

"3Sum is just three nested pointers"

It's sort + fix one element + two pointers on the remainder — O(n²), and the duplicate-skipping at both levels is where most solutions fail.

🎤 Interview Follow-ups

"How do you avoid duplicate triplets in 3Sum without a set?"

Sort first; skip equal neighbors at the outer index and at both inner pointers after recording a hit. A hash-set of triplets works but costs O(n) extra space and hashing overhead.

"When do two pointers beat a hash map for Two Sum?"

When input is already sorted (O(1) space vs O(n)), when memory is constrained, or when you must return values not indices. Hash wins on unsorted input needing indices.

"Why does mid not advance after swapping with hi in Sort Colors?"

The element swapped in from hi is unexamined — it could be a 0 that still needs to move left. Elements from lo are always already-classified, so mid can advance there.