Two Pointers

Quick Revisit

• USE WHEN: Find pair in sorted array, or longest/shortest subarray with a constraint
• INVARIANT: Each pointer moves at most N times total and never backtracks—O(N) guaranteed
• TIME: O(n) | SPACE: O(1)
• CLASSIC BUG: Applying two pointers when the window property is not monotonic (e.g., arrays with negative numbers)
• PRACTICE: ../12-practice-ladders/01-ladder-1100-to-1400.md

The key move is recognizing that you never need to backtrack: each pointer advances at most $n$ times, turning an $O(n^2)$ brute force into a single $O(n)$ sweep.

Difficulty: Beginner | Prerequisites: Sorting and Searching, Binary Search | CF Rating Range: 1000–1400

Every pointer movement eliminates an entire region of the search space—that is the whole secret. The trigger is either "find pair in sorted array" or "longest subarray with constraint" combined with an $O(n)$ requirement. The technique splits into two variants—opposite-direction (sorted pair queries) and same-direction (sliding window)—and the mnemonic "SOME" captures the checklist: Sort if needed, Opposite vs same direction, Monotonicity check, Each pointer moves at most $n$ times.

The historical roots run deep: the merge step of merge sort (von Neumann, 1945) is opposite-direction two pointers in disguise. The pair-sum variant spread through programming interviews in the 2000s; the same-direction variant traces to string-matching algorithms from the 1970s. The bookshelf analogy is concrete: two people searching a sorted shelf from opposite ends—one from 'A' heading right, one from 'Z' heading left—will meet at the target without either scanning the whole shelf. Where the analogy breaks: both pointers index the same sorted array, not two separate walls. The structural requirement is sorted order; without it the technique collapses entirely.

Contest Frequency: ★★★ Common—appears in most contests

---

Contents

• If I Had 5 Minutes
• Intuition
• Pointer Movement Traces
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Solve With Me
• Further Reading
• What to Solve Next

---

If I Had 5 Minutes

• Two patterns: opposite-direction (sorted pair finding) and same-direction (subarray with constraint)—pick the wrong one and you'll fight the code the whole way
• Sort first for opposite-direction; preserve array order for same-direction
• Each pointer moves at most $N$ times → $O(N)$ total, always; the amortized argument is the proof
• If the window property isn't monotonic (e.g., negative numbers in a sum constraint), two pointers will silently give wrong answers—reach for prefix sums instead
• Three-sum: fix one element with an outer loop, then two-pointer on the rest → $O(N^2)$

---

Intuition

You have a sorted array: [2, 4, 5, 7, 10, 13]. You need to find whether any pair of elements sums to 11.

Your first instinct: check every pair.

// Brute force: check all pairs
for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
        if (a[i] + a[j] == target)
            cout << a[i] << " " << a[j] << "\n";

Let's count the work. With $n=6$ elements, every pair and its sum:

  i=0:  (2,4)=6    (2,5)=7    (2,7)=9    (2,10)=12   (2,13)=15
  i=1:  (4,5)=9    (4,7)=11*  (4,10)=14  (4,13)=17
  i=2:  (5,7)=12   (5,10)=15  (5,13)=18
  i=3:  (7,10)=17  (7,13)=20
  i=4:  (10,13)=23
                                              * = answer

That is $(\genfrac{}{}{0ex}{}{6}{2})=15$ comparisons to find one pair. The answer (4, 7) sits at comparison #7—we wasted 6 checks before it and would waste 8 more after it if we weren't lucky enough to stop early.

And this scales as $O(n^2)$. With $n=\mathrm{200,000}$ the inner loop executes $\sim 2\cdot {10}^{10}$ times—way too slow for a 2-second time limit.

Look at the table above. We checked (2, 13) = 15—clearly too large—and then kept pairing 2 with other large values like 10. We checked (10, 13) = 23—obviously way over—but the nested loop doesn't know any better. Every comparison is independent; the algorithm has no memory of what it has already learned. Each step throws away exactly one data point and no more.

Two pointers—one starting at each end of a sorted array, moving inward—find a target-sum pair in $O(n)$ time, because each comparison eliminates an entire row or column of the pair matrix.

Here is why. When we compute a[L] + a[R]:

• If the sum is too large, no pair involving a[R] with any element $\le$ a[L] can hit the target—they would all be at least this large. a[R] is permanently ruled out; move R left.
• If the sum is too small, no pair involving a[L] with any element $\ge$ a[R] can hit the target—they would all be at most this small. a[L] is permanently ruled out; move L right.

Every comparison kills an entire element from the search. The pointers can each move at most $n$ times, so total work is $O(n)$.

Analogy: narrowing a search corridor. Imagine a long hallway with numbered doors on both walls—ascending on the left, descending on the right. You start at opposite ends. You need two doors (one from each wall) whose numbers sum to a target. If the current pair sums too high, you walk away from the big door. Too low, you walk away from the small one. Each step permanently shortens the corridor; you never backtrack and never revisit a door.

Where the analogy breaks: the hallway metaphor implies two separate sequences. In practice, both pointers index the same sorted array. The critical structural requirement is sorted order—without it, stepping inward does not guarantee a monotonic change in the sum, and the technique collapses. Two pointers is not a general pair-finding trick; it is an exploitation of monotonicity.

Visual Walkthrough

Same array: [2, 4, 5, 7, 10, 13], target $=11$.

  Step 1: a[L] + a[R] = 2 + 13 = 15 > 11  -->  move R left
  +----+----+----+----+----+----+
  |  2 |  4 |  5 |  7 | 10 | 13 |
  +----+----+----+----+----+----+
    ^                         ^
    L                         R
  sum = 15 > target
  Action: R--  (13 cannot pair with anything >= 2 to give 11)

  Step 2: a[L] + a[R] = 2 + 10 = 12 > 11  -->  move R left
  +----+----+----+----+----+----+
  |  2 |  4 |  5 |  7 | 10 | 13 |
  +----+----+----+----+----+----+
    ^                   ^
    L                   R
  sum = 12 > target
  Action: R--  (10 cannot pair with anything >= 2 to give 11)

  Step 3: a[L] + a[R] = 2 + 7 = 9 < 11  -->  move L right
  +----+----+----+----+----+----+
  |  2 |  4 |  5 |  7 | 10 | 13 |
  +----+----+----+----+----+----+
    ^              ^
    L              R
  sum = 9 < target
  Action: L++  (2 cannot pair with anything <= 7 to give 11)

  Step 4: a[L] + a[R] = 4 + 7 = 11 == 11  -->  FOUND!
  +----+----+----+----+----+----+
  |  2 |  4 |  5 |  7 | 10 | 13 |
  +----+----+----+----+----+----+
         ^         ^
         L         R
  sum = 11 = target  -->  answer is (4, 7)

Operation count: 4 comparisons to find the pair. Brute force needed 15 (or 7 if it got lucky and stopped early—but worst case is always 15). That is a $3.75\times$ speedup on just 6 elements.

The gap widens fast. For $n=\mathrm{200,000}$: brute force does up to $\sim 2\cdot {10}^{10}$ comparisons. Two pointers does at most $\mathrm{200,000}$. That is a $\mathrm{100,000}\times$ improvement.

---

The walkthrough above shows the logic for opposite-direction pair-finding. The traces below cover that variant plus three others—same-direction window, merge, and three-sum—so you can see how the indices actually move in each case.

Pointer Movement Traces

Opposite-Direction (Pair Sum)

Array (sorted): [1, 3, 5, 7, 9, 11]  Target = 10

Step 1:  L=0, R=5   a[L]+a[R] = 1+11 = 12 > 10  --> R--
         L->                             <-R
         [1, 3, 5, 7, 9, 11]

Step 2:  L=0, R=4   a[L]+a[R] = 1+9  = 10 = 10  --> FOUND!
         L->                        <-R
         [1, 3, 5, 7, 9, 11]

Same-Direction (Longest Subarray with Sum $\le k$)

Array: [2, 1, 3, 1, 1]  k = 4

Step 1: L=0, R=0  sum=2  <=4  best=1  --> R++
        L
        R
        [2, 1, 3, 1, 1]

Step 2: L=0, R=1  sum=3  <=4  best=2  --> R++
        L  R
        [2, 1, 3, 1, 1]

Step 3: L=0, R=2  sum=6  >4   --> L++, sum-=a[L]=2, sum=4
        L     R
        [2, 1, 3, 1, 1]

Step 4: L=1, R=2  sum=4  <=4  best=2  --> R++
           L  R
        [2, 1, 3, 1, 1]

Step 5: L=1, R=3  sum=5  >4   --> L++, sum-=a[L]=1, sum=4
           L     R
        [2, 1, 3, 1, 1]

Step 6: L=2, R=3  sum=4  <=4  best=2  --> R++
              L  R
        [2, 1, 3, 1, 1]

Step 7: L=2, R=4  sum=5  >4   --> L++, sum-=a[L]=3, sum=2
              L     R
        [2, 1, 3, 1, 1]

Step 8: L=3, R=4  sum=2  <=4  best=2  --> done (R reached end)
                 L  R
        [2, 1, 3, 1, 1]

Answer: best = 2 (e.g., subarrays [2,1], [1,3], [3,1], [1,1] all have length 2)

Merging Two Sorted Arrays

A: [1, 4, 7]    B: [2, 5, 6]
    i                j

Step 1: A[i]=1 < B[j]=2  --> take 1, i++    Result: [1]
Step 2: A[i]=4 > B[j]=2  --> take 2, j++    Result: [1, 2]
Step 3: A[i]=4 < B[j]=5  --> take 4, i++    Result: [1, 2, 4]
Step 4: A[i]=7 > B[j]=5  --> take 5, j++    Result: [1, 2, 4, 5]
Step 5: A[i]=7 > B[j]=6  --> take 6, j++    Result: [1, 2, 4, 5, 6]
Step 6: B exhausted       --> take 7, i++    Result: [1, 2, 4, 5, 6, 7]

Three-Sum Reduction

Array (sorted): [1, 2, 3, 4, 5]  Target = 9

Fix a[0]=1, find pair summing to 8 in [2, 3, 4, 5]:
  L=1, R=4: 2+5=7 < 8 --> L++
  L=2, R=4: 3+5=8 = 8 --> FOUND triple (1, 3, 5)

Fix a[1]=2, find pair summing to 7 in [3, 4, 5]:
  L=2, R=4: 3+5=8 > 7 --> R--
  L=2, R=3: 3+4=7 = 7 --> FOUND triple (2, 3, 4)

The Invariant

+------------------------------------------------------------------+
| INVARIANT: At every step, all pairs (i, j) where i < L or        |
| j > R have already been implicitly eliminated. The answer, if     |
| it exists, satisfies L <= i < j <= R.                             |
+------------------------------------------------------------------+

Why it holds. Each pointer move eliminates exactly one element from consideration, and that element cannot be part of any valid pair with the remaining candidates:

• Step 1 set R from 5 to 4—eliminating a[5] = 13. Why safe? a[0] + a[5] = 15 > 11, and a[0] = 2 is the smallest remaining element. So a[i] + a[5] >= 15 > 11 for every $i$ in $[L,R]$. No remaining element can pair with 13 to hit 11.

• Step 2 set R from 4 to 3—eliminating a[4] = 10. Why safe? a[0] + a[4] = 12 > 11, and by the same argument, a[i] + a[4] >= 12 > 11 for all remaining $i$.

• Step 3 set L from 0 to 1—eliminating a[0] = 2. Why safe? a[0] + a[3] = 9 < 11, and a[3] = 7 is the largest remaining element. So a[0] + a[j] <= 9 < 11 for every $j$ in $[L,R]$. No remaining element can pair with 2 to reach 11.

At Step 4, the invariant still holds: the unexplored region $[1,3]$ contains the answer (4, 7), and we find it immediately.

The algorithm is just a loop that preserves this invariant until either a match is found or $L\ge R$ (all pairs exhausted).

What the Code Won't Teach You

The monotone invariant must be rigorous, not felt. Before writing a two-pointer solution, state explicitly: "Once lo passes position $i$, it never needs to return to $i$. Why? Because ..." and complete that sentence. If you cannot complete it, two pointers may not be correct. The code compiles either way—the invariant is what separates correct from silently wrong.

Sorting is not optional for opposite-direction two pointers. On an unsorted array, "a[lo] + a[hi] > target → move hi left" is meaningless—moving hi left does not guarantee a smaller value. The sorted invariant $a[0]\le a[1]\le \dots \le a[n-1]$ is what makes each pointer movement eliminate an entire row or column of the pair matrix.

  WHY SORTED ORDER MATTERS -- THE PAIR MATRIX VIEW
  =================================================

  Sorted: a = [1, 3, 5, 7, 9]    target = 10

  Pair-sum matrix (upper triangle):
            a[0] a[1] a[2] a[3] a[4]
  a[0]  1    -    4    6    8   10OK
  a[1]  3         -    8   10OK  12
  a[2]  5              -   12   14
  a[3]  7                   -   16
  a[4]  9                        -

  Two pointers trace a staircase path:
  Start at (0,4)=10 -> FOUND.

  Each "move hi left" eliminates the rightmost COLUMN.
  Each "move lo right" eliminates the topmost ROW.
  Total cells visited <= n. Without sorted order,
  the matrix has no monotone structure -- no staircase exists.

Counting pairs vs. finding pairs vs. outputting all pairs are different problems. "Does a pair with sum $k$ exist?"—stop at first find, $O(n)$. "Count all pairs with sum $k$"—continue past duplicates, $O(n)$. "Output all pairs"—potentially $O(n^2)$ output for degenerate input. Know which variant your problem requires.

When to Reach for This

Trigger phrases in problem statements:

• "Find a pair with sum equal to / closest to $X$"—classic opposite-direction two pointers on a sorted array.
• "Sorted array" combined with two conditions to satisfy—sorted order is the structural prerequisite.
• "Merge two sorted sequences"—two pointers, one in each array, always advancing the smaller head.
• "Longest subarray / substring satisfying ..."—same-direction (caterpillar) variant with a sliding window.
• $n\le 2\cdot {10}^5$ and the naive solution is $O(n^2)$—strong hint that an $O(n)$ or $O(n\log n)$ technique is needed.

Counter-examples—when two pointers does NOT work:

• Unsorted data for pair-finding. Opposite-direction two pointers requires sorted input. If you cannot sort (e.g., original indices matter for the answer), use a hash map for $O(n)$ expected time instead.
• Non-monotonic window constraints. Same-direction two pointers requires that if window $[l,r]$ violates the constraint, extending to $[l,r+1]$ cannot fix it—you must shrink from the left. If both extending and shrinking can repair a violation, the constraint is non-monotonic and two pointers gives wrong answers. Use a deque, segment tree, or binary search on prefix sums instead.
• Negative numbers in subarray-sum problems. If elements can be negative, a wider window can have a smaller sum than a narrower one. The monotonicity assumption breaks and two pointers silently produces wrong answers. Use prefix sums + sorting or a balanced BST.

---

C++ STL Reference

Two pointers rarely needs exotic library support, but these utilities come up often as building blocks.

Function / Class	Header	What it does	Time Complexity
sort(begin, end)	<algorithm>	Sort range; required before opposite-direction two pointers	$O(n\log n)$
unique(begin, end)	<algorithm>	Remove consecutive duplicates, returns new logical end	$O(n)$
lower_bound(begin, end, val)	<algorithm>	Iterator to first element $\ge$ val (sorted range)	$O(\log n)$
upper_bound(begin, end, val)	<algorithm>	Iterator to first element $>$ val (sorted range)	$O(\log n)$
distance(first, last)	<iterator>	Number of steps from first to last	$O(1)$ for random-access
accumulate(begin, end, init)	<numeric>	Sum of range (useful for verifying window sums)	$O(n)$
vector<T>::begin() / end()	<vector>	Random-access iterators to first / past-the-end	$O(1)$

---

Implementation (Contest-Ready)

Pair with Target Sum—Minimal

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());

    int lo = 0, hi = n - 1;
    while (lo < hi) {
        // Invariant: answer, if it exists, has indices in [lo, hi]
        int s = a[lo] + a[hi];
        if (s == target) {
            cout << a[lo] << " " << a[hi] << "\n";
            return 0;
        }
        if (s < target) ++lo;
        else --hi;
    }
    cout << "No pair found\n";
}

Pair with Target Sum—Annotated

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, target;
    cin >> n >> target;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    // Two pointers on sorted data: O(n log n) sort + O(n) scan
    sort(a.begin(), a.end());

    int lo = 0, hi = n - 1;
    while (lo < hi) {
        // Invariant: all pairs (i,j) with i < lo or j > hi have been eliminated
        int s = a[lo] + a[hi];
        if (s == target) {
            cout << a[lo] << " " << a[hi] << "\n";
            return 0;
        }
        // If sum too small, we need a larger left value --> advance lo
        // If sum too large, we need a smaller right value --> retreat hi
        if (s < target) ++lo;
        else --hi;
    }
    // lo == hi means all pairs exhausted
    cout << "No pair found\n";
}

Longest Subarray with Sum $\le k$—Minimal

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    long long sum = 0;
    int ans = 0;
    for (int l = 0, r = 0; r < n; ++r) {
        // Invariant: sum == a[l] + a[l+1] + ... + a[r] after adding a[r]
        sum += a[r];
        while (sum > k) sum -= a[l++];
        ans = max(ans, r - l + 1);
    }
    cout << ans << "\n";
}

Longest Subarray with Sum $\le k$—Annotated

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    long long sum = 0;
    int ans = 0;

    // l = left boundary of window, r = right boundary
    // Invariant: sum = a[l] + a[l+1] + ... + a[r]
    for (int l = 0, r = 0; r < n; ++r) {
        sum += a[r];  // expand window to include a[r]

        // Shrink from the left until the window satisfies the constraint
        while (sum > k)
            sum -= a[l++];

        // Window [l..r] is valid; update best answer
        ans = max(ans, r - l + 1);
    }
    cout << ans << "\n";
}

---

Operations Reference

Both variants are linear—the key difference is whether the sort you need before an opposite-direction scan dominates the total cost.

Operation	Time	Space	Notes
Opposite-direction scan	$O(n)$	$O(1)$	Requires sorted input
Same-direction scan	$O(n)$	$O(1)$	Each pointer moves at most $n$ times
Sort (prerequisite)	$O(n\log n)$	$O(\log n)$	Needed for opposite-direction
Total (opposite)	$O(n\log n)$	$O(n)$	Dominated by sort + input storage
Total (same-direction)	$O(n)$	$O(n)$	Input storage only

---

Problem Patterns & Tricks

Pair Sum / Two Sum (Sorted)

Sort the array. Use opposite-direction pointers. If a[lo] + a[hi] < target, increment lo; if greater, decrement hi.

Works because sorting creates a monotonic structure: moving lo right can only increase the sum, moving hi left can only decrease it.

sort(a.begin(), a.end());
int lo = 0, hi = n - 1;
while (lo < hi) {
    // Invariant: answer pair (i,j) satisfies lo <= i < j <= hi
    if (a[lo] + a[hi] == target) { /* found */ break; }
    if (a[lo] + a[hi] < target) ++lo; else --hi;
}

CF examples: CF 1538C -- Number of Pairs, CF 1030B -- Vasya and Cornfield

Merge Two Sorted Arrays / Sequences

Two pointers, one in each array. Compare heads, take the smaller. This is the merge step of merge sort and appears in problems involving sorted sequences.

int i = 0, j = 0;
while (i < n && j < m) {
    // Invariant: merged[0..i+j-1] contains all elements < min(a[i], b[j]) in sorted order
    if (a[i] <= b[j]) merged.push_back(a[i++]);
    else merged.push_back(b[j++]);
}
while (i < n) merged.push_back(a[i++]);   // Invariant: remaining a[i..n-1] > all of b
while (j < m) merged.push_back(b[j++]);   // Invariant: remaining b[j..m-1] > all of a

CF examples: CF 1165C -- Good String, CF 1462C -- Unique Number

Remove Duplicates In-Place

Same-direction with a "write pointer" and a "read pointer." The write pointer marks where the next unique element goes.

sort(a.begin(), a.end());
int w = 0;
for (int r = 0; r < n; ++r)
    if (r == 0 || a[r] != a[r - 1])
        a[w++] = a[r];
// a[0..w-1] contains unique elements

STL shortcut: a.erase(unique(a.begin(), a.end()), a.end()); after sorting.

CF examples: CF 1352C -- K-th Not Divisible by n

Longest Substring / Subarray with Constraint

Same-direction pointers maintaining a window [l, r]. Expand r; when constraint breaks, shrink l. Works when the constraint is monotonic: if [l, r] is invalid, so is [l, r+1].

Common constraints: sum $\le k$, at most $k$ distinct elements, no repeated characters.

int ans = 0;
for (int l = 0, r = 0; r < n; ++r) {
    // add a[r] to window state
    while (/* window invalid */)
        // remove a[l] from window state, ++l
    ans = max(ans, r - l + 1);
}

CF examples: CF 1611C -- Polycarp Recovers the Permutation, CF 279B -- Books

Count Pairs with Sum in Range $[lo,hi]$

Count pairs with sum $\le hi$ minus count with sum $\le lo-1$. Each count uses opposite-direction two pointers on a sorted array.

auto count_le = [&](long long bound) -> long long {
    long long cnt = 0;
    int l = 0, r = n - 1;
    while (l < r) {
        if (a[l] + a[r] <= bound) {
            cnt += r - l;  // all pairs (l, l+1), ..., (l, r) are valid
            ++l;
        } else --r;
    }
    return cnt;
};
long long ans = count_le(hi) - count_le(lo - 1);

CF examples: CF 1538C -- Number of Pairs

Three Sum / k-Sum Reduction

Fix one element with an outer loop; reduce to two-sum on the remaining subarray. Total: $O(n^2)$ for 3-sum, $O(n^{k-1})$ in general.

sort(a.begin(), a.end());
for (int i = 0; i < n; ++i) {
    int lo = i + 1, hi = n - 1;
    while (lo < hi) {
        int s = a[i] + a[lo] + a[hi];
        if (s == target) { /* found triple */ ++lo; --hi; }
        else if (s < target) ++lo;
        else --hi;
    }
}

CF examples: CF 1692F -- 3SUM

---

Contest Cheat Sheet

+---------------------------------------------------------------+
|                     TWO POINTERS (AL-02)                      |
+---------------------------------------------------------------+
| WHEN TO USE:                                                  |
|  - "Find pair/subarray" + n <= 2e5 (need O(n) or O(n log n)) |
|  - Sorted input or you can sort without losing info           |
|  - Monotonic window property: shrink fixes violations         |
+---------------------------------------------------------------+
| OPPOSITE-DIRECTION (sorted, pair queries):                    |
|   sort(a.begin(), a.end());                                   |
|   int lo = 0, hi = n-1;                                      |
|   while (lo < hi) {                                           |
|       if (a[lo]+a[hi] == t) { /*found*/ ++lo; --hi; }        |
|       else if (a[lo]+a[hi] < t) ++lo; else --hi;             |
|   }                                                           |
+---------------------------------------------------------------+
| SAME-DIRECTION (subarray / window):                           |
|   for (int l=0, r=0; r<n; ++r) {                             |
|       // add a[r]                                             |
|       while (/* invalid */) // remove a[l], ++l               |
|       ans = max(ans, r-l+1);                                  |
|   }                                                           |
+---------------------------------------------------------------+
| COMPLEXITY:  O(n) scan + O(n log n) if sorting needed         |
| SPACE:       O(1) extra (beyond input)                        |
+---------------------------------------------------------------+
| WATCH OUT:   sort first | lo < hi not lo <= hi | overflow     |
+---------------------------------------------------------------+

---

Gotchas & Debugging

Common Mistakes

• Forgot to sort. Opposite-direction two pointers is only correct on sorted data. If your answer is wrong, check this first.

• lo < hi vs lo <= hi. For pair problems, use lo < hi (strict)—you cannot pair an element with itself. Using <= gives wrong answers or infinite loops.

• Integer overflow. a[lo] + a[hi] can overflow int if values are up to ${10}^9$. Cast to long long: (long long)a[lo] + a[hi].

• Duplicate counting. If the problem asks for distinct pairs, skip duplicates after finding a match:

  while (lo < hi && a[lo] == a[lo + 1]) ++lo;
  while (lo < hi && a[hi] == a[hi - 1]) --hi;
  ++lo; --hi;

• Same-direction: non-monotonic constraint. Two pointers only works if the window property is monotonic. If adding an element can both help and hurt, two pointers is wrong—consider a different approach (e.g., sliding window with a deque, or binary search).

• Empty window. If all elements individually violate the constraint, your left pointer can pass your right pointer. Guard with while (l <= r && ...) or ensure the constraint always holds for single elements.

• Negative numbers in same-direction. If array elements can be negative, the window sum is not monotonic in window size. Sort + opposite-direction, or use prefix sums + binary search instead.

• Debugging tip: Print lo, hi (or l, r) and the current window state at each step. A two-pointer bug almost always shows up as a pointer going the wrong direction or not advancing.

Mental Traps

"I can always replace nested loops with two pointers." Two pointers only reduces $O(n^2)$ to $O(n)$ when there is a monotone invariant: once you move a pointer past a position, you never need to come back. If revisiting positions is necessary, two pointers does not apply. The nested loop is not automatically replaceable—you must prove the monotone invariant first.

  WHEN TWO POINTERS REPLACES A NESTED LOOP
  ==========================================

  Nested loop:          Two pointers:
  for i in 0..n:        lo = 0, hi = n-1
    for j in i+1..n:    while lo < hi:
      check(i, j)         check(lo, hi)
                           advance one pointer
  O(n^2)                 O(n)

  WORKS when: each pointer move provably eliminates
  all remaining pairs involving the discarded position.

  FAILS when: discarding a position might skip a valid pair
  that can't be reached by the remaining pointer positions.

"Two pointers works on 2D arrays too." Naively applying two pointers in two dimensions simultaneously almost never works. For 2D problems (e.g., finding a sub-rectangle with a certain sum), you typically fix one dimension with an outer loop and apply two pointers on the other. This gives $O(n^2)$ or $O(n^2\log n)$, not $O(n)$.

---

Self-Test

Close the file and answer these from memory. If any one stumps you, re-read that section before moving on.

• [ ] Write the two-pointer solution for "count pairs in a sorted array with sum = target"—include duplicate-skipping logic.
• [ ] State the amortized $O(n)$ argument for both opposite-direction and same-direction two pointers.
• [ ] Explain why two pointers for pair-sum requires sorted input, using the monotone invariant.
• [ ] Distinguish the from-both-ends pattern from the sliding window (same-direction) pattern—state the use case for each.
• [ ] Give an example where applying two pointers to an unsorted array produces a wrong answer.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Books	CF 279B	Easy (1400)	Same-direction, max subarray with sum $\le t$
2	Number of Pairs	CF 1538C	Easy (1300)	Opposite-direction, count pairs with sum in range
3	Cellular Network	CF 702C	Easy (1400)	Two pointers + binary search variant
4	Two Pointers Step 1 (EDU)	CF EDU	Easy	Full tutorial course with graded problems
5	Worms	CF 474B	Easy (1200)	Prefix sums + two pointer / binary search
6	3SUM	CF 1692F	Medium (1300)	Fix one, two-pointer on rest
7	Good String	CF 1165C	Medium (1300)	Two pointers on two sequences
8	Berland Fair	CF 1073C	Medium (1600)	Simulation + careful pointer management
9	Segment with Small Sum	CSES	Easy	Classic opposite-direction two sum
10	Sum of Three Values	CSES	Medium	3-sum reduction to two pointers

---

Solve With Me -- CF 1462D "Add to Neighbour and Remove"

The problem: I have an array, and each operation lets me add an element to its left or right neighbor and then delete it. I want the minimum operations to make all remaining elements equal. Concretely: after some deletions, the surviving elements are contiguous groups whose sums are all the same—minimize the number of removed elements.

My brain immediately goes: brute-force all possible partitions into equal-sum groups? But $n$ up to $3\times {10}^5$, that's not happening.

Wait—let me think about what the final array looks like. It's some number of groups of consecutive elements, all with the same sum. That sum must divide the total. So I can iterate over the number of surviving elements $k$ from $n$ down to $1$: if $\text{total}/k$ is an integer, check if I can partition the array into groups each summing to $\text{total}/k$. The answer is $n-k$.

But I don't even need to iterate $k$. I can iterate over possible target sums: the target must be $\text{total}/k$ for some $k$, so it must divide the total. And I want maximum $k$ (fewest removals), which means the smallest valid target sum.

Hmm, but the smallest target that works isn't just any divisor—the array has to be greedily partitionable. Let me just try all possible target sums from small to large. For each candidate $T$, sweep left to right with a running sum; whenever it hits $T$, start a new group. If the running sum ever exceeds $T$, this target is impossible.

Actually even simpler: I try target sums $T$ in order of $n-k$ ascending (i.e., $k=n,n-1,n-2,\dots ,1$). For each $k$, if $\text{total}modk\ne 0$, skip. Otherwise set $T=\text{total}/k$ and do the greedy sweep. First valid $k$ gives the answer. Worst case I try $O(n)$ values of $k$, each sweep is $O(n)$, so $O(n^2)$—which is fine for $n\le 3\times {10}^5$... actually $9\times {10}^{10}$, that's too slow!

No wait—the number of divisors of $\text{total}$ is at most a few hundred. So I only need to check $O(d(\text{total}))$ candidates, each in $O(n)$. That's completely fine. But actually I'm iterating $k$ from $n$ down to $1$ and skipping non-divisors, so it's really $O(n+d\cdot n)$... either way it's fast in practice. Submitted, AC.

What to recognize next time: When "make all elements equal" appears, think about what the target value must be. The target constrains the total, and greedy partitioning validates each candidate. Two-pointer / sweep logic does the checking.

---

Further Reading

• cp-algorithms—Two Pointers—formal correctness argument and more patterns.
• CF EDU—Two Pointers—interactive course with judge.
• Errichto—Two Pointers (YouTube)—video walkthrough of common patterns.
• See: 06-sliding-window.md—extends same-direction two pointers with auxiliary data structures.
• See: 04-binary-search.md—alternative to two pointers when the window property is not monotonic.
• See: 07-prefix-sums.md—handles subarray sums with negative numbers where two pointers fails.

---

What to Solve Next

Two pointers is a building block, not an endpoint. Here is where the pattern extends and where to go deeper:

• Sliding Window—06-sliding-window.md. The same-direction variant generalizes into sliding window when you need auxiliary data structures (deques, maps) to maintain window state. Read this next if subarray/substring problems are your focus.
• Binary Search—04-binary-search.md. When the window property is not monotonic but the answer space is, binary search on the answer replaces two pointers. Also pairs naturally with two pointers in problems like "minimize the maximum."
• Sorting and Searching—03-sorting-and-searching.md. Opposite-direction two pointers requires sorted input. Strengthen your sorting foundations if you are not yet comfortable with custom comparators and coordinate compression.
• Prefix Sums—07-prefix-sums.md. When elements can be negative, two pointers on subarray sums breaks. Prefix sums + sorting or prefix sums + binary search handle these cases.
• Practice Ladder (1100–1400)—../12-practice-ladders/01-ladder-1100-to-1400.md. Curated problems at the right difficulty to drill these patterns until they are automatic.