AntInLoop

Two Pointers Technique

The Two Pointers technique uses two indices moving monotonically across a sorted array or sequence to solve pair-sum, partitioning, deduplication, and container problems in O(n) time and O(1) space.

Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code

Two Pointers Technique

The Two Pointers technique replaces nested $O(n^2)$ loops with two indices (left and right, or slow and fast) that move monotonically across an array or linked list. Because each pointer advances at most $n$ times, the total work drops to $O(n)$ time and $O(1)$ auxiliary space!

At a Glance

| Pattern | Pointer Movement | Classic Uses |

| :--- | :--- | :--- |

| Opposite Ends | l = 0, r = n - 1 moving inward | Two Sum (sorted), Container With Most Water, Trapping Rain Water, Palindrome check |

| Fast / Slow (Same Direction) | slow writes/lags, fast scans ahead | In-place deduplication, moving zeros, linked-list cycle detection (Floyd) |

| Two Arrays | i in A, j in B | Merging sorted arrays, intersection of sorted arrays |

---

How It Works (Opposite-Ends Pattern)

On a sorted array, suppose we want a pair (l, r) with A[l] + A[r] == target:

1. Start at l = 0, r = n - 1.

2. While l < r:

  • If A[l] + A[r] == target, return {l, r}.
  • If A[l] + A[r] < target, we need a larger sum → ++l.
  • Else we need a smaller sum → --r.

Step-by-Step Trace (A = [1, 2, 4, 7, 11, 15], target = 15)

  • l=0 (1), r=5 (15) → 16 > 15 → --r
  • l=0 (1), r=4 (11) → 12 < 15 → ++l
  • l=1 (2), r=4 (11) → 13 < 15 → ++l
  • l=2 (4), r=4 (11) → 15 == 15 → return (2, 4)!

---

Complexity & Key Insights

  • Why It's $O(n)$: Every iteration either increments l or decrements r, so the distance r - l strictly decreases by 1 per step—at most $n - 1$ iterations total.
  • When Two Pointers Applies: You need a monotonicity invariant—discarding an index (++l or --r) must be mathematically guaranteed never to discard the optimal answer.

---

Practice Problems

Easy

1. Two Sum II — Sorted Array (LeetCode 167)

Find 0-based indices (i, j) in a sorted array summing to target.

Approach: Opposite-end pointers l = 0, r = n - 1. Time: $O(n)$. Space: $O(1)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <utility>
#include <vector>

std::pair<int, int> twoSumSorted(const std::vector<int>& a, int target) {
    int l = 0, r = static_cast<int>(a.size()) - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == target) return {l, r};
        if (s < target) ++l;
        else --r;
    }
    return {-1, -1};
}

int main() {
    auto [i, j] = twoSumSorted({1, 2, 4, 7, 11, 15}, 15);
    std::cout << i << " " << j << "\n"; // 2 4
    return 0;
}

</details>

2. Remove Duplicates from Sorted Array In-Place (LeetCode 26)

Remove duplicates in-place and return the new length k.

Approach: Fast/slow pointers: slow marks the last unique written slot; whenever nums[fast] != nums[slow], advance slow and copy nums[fast]. Time: $O(n)$. Space: $O(1)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

int removeDuplicates(std::vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < static_cast<int>(nums.size()); ++fast) {
        if (nums[fast] != nums[slow]) nums[++slow] = nums[fast];
    }
    return slow + 1;
}

int main() {
    std::vector<int> a = {1, 1, 2, 2, 3, 4, 4};
    int k = removeDuplicates(a);
    for (int i = 0; i < k; ++i) std::cout << a[i] << " ";
    std::cout << "\n";
    return 0;
}

</details>

---

Intermediate

3. Container With Most Water (LeetCode 11)

Given vertical line heights h[0..n-1], find two lines forming a container holding the maximum water min(h[l], h[r]) * (r - l).

Approach: Start at l = 0, r = n - 1. Always move the shorter wall inward—moving the taller wall can only decrease width without ever increasing the limiting height! Time: $O(n)$. Space: $O(1)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

int maxArea(const std::vector<int>& h) {
    int l = 0, r = static_cast<int>(h.size()) - 1, best = 0;
    while (l < r) {
        best = std::max(best, std::min(h[l], h[r]) * (r - l));
        if (h[l] < h[r]) ++l;
        else --r;
    }
    return best;
}

int main() {
    std::cout << maxArea({1, 8, 6, 2, 5, 4, 8, 3, 7}) << "\n"; // 49
    return 0;
}

</details>

4. 3Sum (Unique Triplets Summing to Zero, LeetCode 15)

Find all unique triplets (a, b, c) in nums that sum to 0.

Approach: Sort nums, fix i (skipping duplicates), and run opposite-end Two Pointers on [i + 1, n - 1] for -nums[i] (skipping duplicate l and r). Time: $O(n^2)$. Space: $O(1)$ extra.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

std::vector<std::vector<int>> threeSum(std::vector<int> nums) {
    std::sort(nums.begin(), nums.end());
    int n = static_cast<int>(nums.size());
    std::vector<std::vector<int>> res;
    for (int i = 0; i < n - 2; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int l = i + 1, r = n - 1;
        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];
            if (s == 0) {
                res.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l + 1]) ++l;
                while (l < r && nums[r] == nums[r - 1]) --r;
                ++l; --r;
            } else if (s < 0) ++l;
            else --r;
        }
    }
    return res;
}

int main() {
    auto trips = threeSum({-1, 0, 1, 2, -1, -4});
    std::cout << "Triplets: " << trips.size() << "\n"; // 2
    return 0;
}

</details>

---

Hard

5. Trapping Rain Water in $O(1)$ Space (LeetCode 42)

Given an elevation map height[], compute how much water it traps after raining in $O(n)$ time and $O(1)$ space.

Approach: Maintain l, r and running leftMax, rightMax. Whichever side has the smaller max (leftMax <= rightMax) determines the exact water level at that pointer (leftMax - height[l]), so advance that side! Time: $O(n)$. Space: $O(1)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

int trapWater(const std::vector<int>& h) {
    int l = 0, r = static_cast<int>(h.size()) - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (l < r) {
        if (h[l] <= h[r]) {
            leftMax = std::max(leftMax, h[l]);
            water += leftMax - h[l++];
        } else {
            rightMax = std::max(rightMax, h[r]);
            water += rightMax - h[r--];
        }
    }
    return water;
}

int main() {
    std::cout << trapWater({0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}) << "\n"; // 6
    return 0;
}

</details>

---

Related Algorithms