Блог пользователя Nourhan_Abo-Heba

Автор Nourhan_Abo-Heba, история, 14 месяцев назад, По-английски

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 into O(n) or O(n + m).
  • The key is that both pointers only move forward.
  • The pattern works for merging, counting, and sliding window problems.
  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Wait this is pretty nice

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Good job!