The idea of two pointers is that instead of checking all possible pairs or subarrays with two nested loops (which might be O(n²)), you can often move two indices intelligently so that the total work becomes O(n + m).
This trick is common in merging arrays, counting pairs, or working with subarrays.
1. Merging Two Sorted Arrays in O(n + m)
Naive way: copy both arrays into a big array, then sort → O((n+m) log(n+m)).
But since they are already sorted, we can merge directly:
int n, m;
cin >> n >> m;
vector<int> f(n), s(m);
for (int i = 0; i < n; i++) cin >> f[i];
for (int i = 0; i < m; i++) cin >> s[i];
int l = 0, r = 0;
while (l < n && r < m) {
if (f[l] < s[r]) {
cout << f[l] << " ";
l++;
} else {
cout << s[r] << " ";
r++;
}
}
while (l < n) cout << f[l++] << " ";
while (r < m) cout << s[r++] << " ";
2. Counting How Many Are Smaller
You have a sorted array f and many queries a in increasing order. For each query, print how many elements in f are < a.
int n, m; cin >> n >> m;
vector<int> f(n);
for (int i = 0; i < n; i++) cin >> f[i];
int j = 0;
for (int i = 0; i < m; i++) {
int a; cin >> a;
while (j < n && f[j] < a) j++;
cout << j << " ";
}
Time: O(n + m).
Important: Just because you have a while inside a for does not mean O(n*m) automatically. If j only moves forward and never backtracks, the total work of the inner loop is O(n) over all iterations.
3. Counting Equal Pairs
Two sorted arrays a and b. Count the total pairs (i,j) such that a[i] == b[j].
Example:
a: 1 1 3 3 3 5 8 8
b: 1 3 3 4 5 5 5
We can do this in O(n + m):
int n, m; cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
long long l = 0, r = 0, ans = 0;
for (int i = 0; i < n; i++) {
while (l < m && b[l] < a[i]) l++;
while (r < m && b[r] <= a[i]) r++;
ans += r - l; // number of b's equal to a[i]
}
cout << ans << "\n";
4. Subarray Problems — Sliding Window Pattern
Two pointers become “left” and “right” indices of a window. We grow or shrink the window to maintain some property.
(a) Longest segment with sum ≤ s
int n, s; cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long l = 0, r = 0, ans = 0, sum = 0;
while (l < n) {
while (r < n && sum + a[r] <= s) {
sum += a[r];
r++;
}
ans = max(ans, r - l);
sum -= a[l];
l++;
}
cout << ans;
(b) Smallest segment with sum ≥ s
int n, s; cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long l = 0, r = 0, ans = LLONG_MAX, sum = 0;
while (l < n) {
while (r < n && sum < s) {
sum += a[r];
r++;
}
if (sum >= s) ans = min(ans, r - l);
sum -= a[l];
l++;
}
if (ans == LLONG_MAX) ans = -1;
cout << ans;
5. Generic Two-Pointer Template
Many problems follow the same skeleton:
long long l = 0, r = 0, ans = 0, sum = 0;
while (l < n) {
while (r < n && can_add(r)) {
add(r);
r++;
}
ans = max(ans, r - l); // or min, or something else
remove(l); // usually sum -= a[l];
l++;
}
cout << ans;
6. Sliding Window with Fixed Size (Binary Search on Length)
Sometimes you are asked: What is the maximum size of a segment such that its sum ≤ s You can binary search on the length and check with a fixed-size window:
bool can(int len, const vector<int>& a, int s) {
long long sum = 0;
for (int i = 0; i < len; i++) sum += a[i];
if (sum <= s) return true;
for (int i = len; i < (int)a.size(); i++) {
sum += a[i] - a[i - len];
if (sum <= s) return true;
}
return false;
}
Then binary search on len:
int n, s; cin >> n >> s;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int l = 0, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (can(mid, a, s)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans;
Summary
- Two pointers turn many
O(n²)problems intoO(n)orO(n + m). - The key is that both pointers only move forward.
- The pattern works for merging, counting, and sliding window problems.









Wait this is pretty nice
Good job!