two pointers - Codeforces

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

vlade087's blog

two pointers

By vlade087, 11 years ago, In English

Hello anybody can say me what mean when the problem have a tag two pointers. What mean this approach?

two pointers

vlade087
11 years ago
4

Comments (4)

Write comment?

rlac

11 years ago, # |

Look here

→ Reply

baukaman

11 years ago, # |

One of the recent problems involving two pointers is problem I:Pirate Chest from ICPC world finals 2013

This problem reduces to one-dimensional case: in integer array, for each element you want to find element that is lower than current on the left and right sides.

For every element you keep left and right positions for the element which is less than this element. (initially set to itselft). Iterate over descendant sorted array and update your info about pointers.

The problem's time limit pretty large. But involving some other NlogN approaches (such as fenwick tree) gives TL. By pointers you achieve lower constant.

→ Reply

Among_Us_2008

4 months ago, # |

← Rev. 2 →

+10

→ Reply

Kamado_Tanjiro_2008

4 months ago, # ^ |

Two pointers is really an easy and effective technique that is typically used for searching pairs in a sorted array. Given a sorted array A (sorted in ascending order), having N integers, find if there exists any pair of elements (A[i], A[j]) such that their sum is equal to X.

Illustration :

Let us do discuss the working of two pointer algorithm in brief which is as follows. The algorithm basically uses the fact that the input array is sorted. We start the sum of extreme values (smallest and largest) and conditionally move both pointers. We move left pointer ‘i’ when the sum of A[i] and A[j] is less than X. We do not miss any pair because the sum is already smaller than X. Same logic applies for right pointer j.

Code

#include <bits/stdc++.h>

using namespace std;

bool isPairSum(int A[], int N, int X)
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // as equal i and j means same element
            if (i == j)
                continue;

            // pair exists
            if (A[i] + A[j] == X)
                return true;

            // as the array is sorted
            if (A[i] + A[j] > X)
                break;
        }
    }

    // No pair found with given sum.
    return false;
}

// Driver code
int main()
{
    int arr[] = { 2, 3, 5, 8, 9, 10, 11 };
    int val = 17;
    int arrSize = *(&arr + 1) - arr;
    sort(arr, arr + arrSize); // Sort the array
    // Function call
    cout << isPairSum(arr, arrSize, val);

    return 0;
}

Time Complexity: O(n2). Auxiliary Space: O(1)

Lets solve EDU problem:

step 1:

Merging Arrays

Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v1, v2, v3;

int main() {
    scanf("%d%d", &n, &m);
    v1.resize(n);
    for (auto &x : v1) scanf("%d", &x);
    v2.resize(m);
    for (auto &x : v2) scanf("%d", &x);
    int p1 = 0, p2 = 0;
    while (p1 < n || p2 < m) {
        if (p1 == n) v3.push_back(v2[p2++]);
        else if (p2 == m) v3.push_back(v1[p1++]);
        else if (v1[p1] < v2[p2]) v3.push_back(v1[p1++]);
        else v3.push_back(v2[p2++]);
    }
    for (auto x : v3) printf("%d ", x);
    return 0;
}

Number of Smaller

Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v1, v2;

int main() {
    scanf("%d%d", &n, &m);
    v1.resize(n);
    for (auto &x : v1) scanf("%d", &x);
    v2.resize(m);
    for (auto &x : v2) scanf("%d", &x);
    int p1 = 0;
    for (auto x : v2) {
        if (x <= v1[0]) {
            printf("0 ");
            continue;
        }
        while (p1 < n && v1[p1] < x) ++p1;
        printf("%d ", p1);
    }
    return 0;
}

Number of Equal

Code

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v1, v2;

int main() {
    scanf("%d%d", &n, &m);
    v1.resize(n);
    for (auto &x : v1) scanf("%d", &x);
    v2.resize(m);
    for (auto &x : v2) scanf("%d", &x);
    int p1 = 0, p2 = 0;
    long long ans = 0;
    while (p1 < n && p2 < m) {
        if (v1[p1] == v2[p2]) {
            int num1 = 1, num2 = 1;
            ++p1;
            while (p1 < n && v1[p1] == v1[p1 - 1]) ++num1, ++p1;
            ++p2;
            while (p2 < m && v2[p2] == v2[p2 - 1]) ++num2, ++p2;
            ans += 1ll * num1 * num2;
        } else if (v1[p1] < v2[p2]) {
            ++p1;
            while (p1 < n && v1[p1] == v1[p1 - 1]) ++p1;
        } else if (v1[p1] > v2[p2]) {
            ++p2;
            while (p2 < m && v2[p2] == v2[p2 - 1]) ++p2;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

step 2:

Segment with Small Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0, ans = 0;
    long long sum = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        while (sum > s) {
            sum -= v[l++];
        }
        ans = max(ans, i - l + 1);
    }
    printf("%d\n", ans);
    return 0;
}

Segment with Big Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0, ans = n + 1;
    long long sum = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        if (sum < s) continue;
        while (sum >= s) {
            sum -= v[l++];
        }
        ans = min(ans, i - l + 2);
    }
    if (ans > n) ans = -1;
    printf("%d\n", ans);
    return 0;
}

Number of Segments with Small Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;
vector<long long> v2;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0;
    long long sum = 0, ans = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        while (sum > s) sum -= v[l++];
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Number of Segments with Big Sum

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0;
    long long sum = 0, ans = 0;
    for (int i = 0; i < v.size(); ++i) {
        sum += v[i];
        while (sum >= s) sum -= v[l++];
        ans += l;
    }
    printf("%lld\n", ans);
    return 0;
}

Segments with Small Set

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, k;
vector<int> v;
int Tms[MAXN];

int main() {
    scanf("%d%d", &n, &k);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    long long ans = 0;
    int l = 0, num = 0;
    for (int i = 0; i < n; ++i) {
        if (!Tms[v[i]]++) {
            if (++num > k) {
                while (true) if (--Tms[v[l++]] == 0) break;
            }
        }
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Segments with Small Spread

Code 1

#include <bits/stdc++.h>

using namespace std;

int n;
long long k;
vector<long long> v;
deque<int> Mn, Mx;

int main() {
    scanf("%d%lld", &n, &k);
    v.resize(n);
    for (auto &x : v) scanf("%lld", &x);
    long long ans = 0;
    int l = 0;
    for (int i = 0; i < n; ++i) {
        while (!Mn.empty() && v[Mn.back()] > v[i]) Mn.pop_back();
        while (!Mx.empty() && v[Mx.back()] < v[i]) Mx.pop_back();
        Mn.push_back(i), Mx.push_back(i);
        while (v[Mx.front()] - v[Mn.front()] > k) {
            l++;
            while (Mx.front() < l) Mx.pop_front();
            while (Mn.front() < l) Mn.pop_front();
        }
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Code 2

#include <bits/stdc++.h>

using namespace std;

int n;
long long k;
vector<long long> v;

struct Stack {
    vector<long long> v, mn = {LLONG_MAX}, mx = {LLONG_MIN};
    void push(long long x) {
        v.push_back(x);
        mn.push_back(std::min(mn.back(), x));
        mx.push_back(std::max(mx.back(), x));
    }
    long long max() {
        return mx.back();
    }
    long long min() {
        return mn.back();
    }
    long long pop() {
        long long x = v.back();
        v.pop_back();
        mn.pop_back();
        mx.pop_back();
        return x;
    }
    bool empty() {
        return v.empty();
    }
} s1, s2;

void remove() {
    if (s1.empty()) {
        while (!s2.empty()) s1.push(s2.pop());
    }
    s1.pop();
}

int main() {
    scanf("%d%lld", &n, &k);
    v.resize(n);
    for (auto &x : v) scanf("%lld", &x);
    long long ans = 0;
    int l = 0;
    for (int i = 0; i < n; ++i) {
        s2.push(v[i]);
        while (max(s1.max(), s2.max()) - min(s1.min(), s2.min()) > k) {
            remove();
            l++;
        }
        ans += i - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Coprime Segment

Code

#include <bits/stdc++.h>

using namespace std;


int n;
vector<long long> v;

struct Stack {
    vector<long long> stk, val = {0};
    void push(long long x) {
        stk.push_back(x);
        val.push_back(__gcd(val.back(), x));
    }
    long long top() {
        return val.back();
    }
    long long pop() {
        long long x = stk.back();
        stk.pop_back();
        val.pop_back();
        return x;
    }
    bool empty() {
        return stk.empty();
    }
} s1, s2;

void remove() {
    if (s1.empty()) {
        while (!s2.empty()) s1.push(s2.pop());
    }
    s1.pop();
}

int main() {
    scanf("%d", &n);
    v.resize(n);
    for (auto &x : v) scanf("%lld", &x);
    int l = 0, ans = n + 1;
    for (int i = 0; i < n; ++i) {
        s2.push(v[i]);
        while (__gcd(s1.top(), s2.top()) == 1) {
            remove();
            ans = min(ans, i - l + 1);
            l++;
        }
    }
    if (ans > n) ans = -1;
    printf("%d\n", ans);
    return 0;
}

step 3:

Looped Playlist

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long p;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &p);
    v.resize(n);
    long long total = 0;
    for (auto &x : v) {
        scanf("%d", &x);
        total += x;
    }
    long long ans = (p - v[0]) / total * n + 1, sum = (p - v[0]) / total * total + v[0];
    int l = 0, pos = 0;
    if (sum >= p) l = pos = 0;
    else {
        for (int i = n - 1; i >= 0; --i) {
            sum += v[i];
            ++ans;
            if (sum >= p) {
                pos = l = i;
                break;
            }
        }
    }
    long long len = ans;
    for (int r = 1; r < n; ++r) {
        sum += v[r];
        ++len;
        while (sum >= p) {
            sum -= v[l++];
            l %= n;
            --len;
        }
        if (len + 1 < ans) {
            pos = (l - 1 + n) % n;
            ans = len + 1;
        }
    }
    printf("%d %lld\n", pos + 1, ans);
    return 0;
}

Total Length

Code

#include <bits/stdc++.h>

using namespace std;

int n;
long long s;
vector<int> v;

int main() {
    scanf("%d%lld", &n, &s);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0;
    long long ans = 0, sum = 0;
    for (int r = 0; r < n; ++r) {
        sum += v[r];
        while (sum > s) sum -= v[l++];
        ans += 1ll * (r - l + 2) * (r - l + 1) / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

Che city

Code

#include <bits/stdc++.h>

using namespace std;

int n, s;
vector<int> v;

int main() {
    scanf("%d%d", &n, &s);
    v.resize(n + 1);
    for (int i = 1; i <= n; ++i) scanf("%d", &v[i]);
    int l = 1;
    long long ans = 1ll * n * (n + 1) / 2;
    for (int r = 1; r <= n; ++r) {
        while (v[r] - v[l] > s) ++l;
        ans -= r - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Stylish clothes

Code

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> v;
int a[4], b[4];

int main() {
    for (int i = 0, n; i < 4; ++i) {
        scanf("%d", &n);
        for (int j = 0, x; j < n; ++j) {
            scanf("%d", &x);
            v.push_back({x, i});
        }
    }
    sort(v.begin(), v.end());
    int l = 0, num = 0, ans = INT_MAX;
    int ll = 0, rr = 0;
    for (int r = 0; r < v.size(); ++r) {
        if (!b[v[r].second]++) ++num;
        if (num < 4) continue;
        while (b[v[l].second] > 1) {
            --b[v[l++].second];
        }
        if (ans > v[r].first - v[l].first) {
            ans = v[r].first - v[l].first;
            ll = l, rr = r;
        }
    }
    a[v[ll].second] = v[ll].first;
    a[v[rr].second] = v[rr].first;
    for (int i = ll + 1; i < rr; ++i) {
        if (!a[v[i].second]) a[v[i].second] = v[i].first;
    }
    for (int i = 0; i < 4; ++i) printf("%d ", a[i]);
    return 0;
}

Knapsack on a Segment

Code

#include <bits/stdc++.h>

using namespace std;

int n, s;
vector<int> w, c;

int main() {
    scanf("%d%d", &n, &s);
    w.resize(n);
    c.resize(n);
    for (auto &x : w) scanf("%d", &x);
    for (auto &x : c) scanf("%d", &x);
    int l = 0, sumw = 0;
    long long sumc = 0, ans = 0;
    for (int r = 0; r < n; ++r) {
        sumw += w[r];
        sumc += c[r];
        while (sumw > s) {
            sumw -= w[l];
            sumc -= c[l++];
        }
        ans = max(ans, sumc);
    }
    printf("%lld\n", ans);
    return 0;
}

Card Substrings

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n, m;
char s[MAXN], t[MAXN];
int Num[200], a[200];

int main() {
    scanf("%d%d%s%s", &n, &m, s, t);
    for (int i = 0; i < m; ++i) ++Num[t[i]];
    int l = 0;
    long long ans = 0;
    for (int r = 0; r < n; ++r) {
        if (++a[s[r]] > Num[s[r]]) {
            while (s[l] != s[r]) {
                --a[s[l++]];
            }
            --a[s[l++]];
        }
        ans += r - l + 1;
    }
    printf("%lld\n", ans);
    return 0;
}

Not Very Rude Substring

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 5;

int n;
long long c;
char s[MAXN];

int main() {
    scanf("%d%lld%s", &n, &c, s);
    int l = 0, ans = 0, numa = 0, numb = 0;
    long long sum = 0;
    for (int r = 0; r < n; ++r) {
        if (s[r] == 'a') ++numa;
        else if (s[r] == 'b') {
            ++numb;
            sum += numa;
        }
        while (sum > c) {
            if (s[l] == 'a') {
                sum -= numb;
                --numa;
            } else if (s[l] == 'b') --numb;
            ++l;
        }
        ans = max(ans, r - l + 1);
    }
    printf("%d\n", ans);
    return 0;
}

A-B Knapsack

Code

#include <bits/stdc++.h>

using namespace std;

int n, m, s, a, b;
vector<int> va, vb;

int main() {
    scanf("%d%d%d%d%d", &n, &m, &s, &a, &b);
    va.resize(n);
    vb.resize(m);
    for (auto &x : va) scanf("%d", &x);
    for (auto &x : vb) scanf("%d", &x);
    sort(va.begin(), va.end(), greater<int>());
    sort(vb.begin(), vb.end(), greater<int>());
    int r = min(n, s / a) - 1, sum = (r + 1) * a;
    long long ans = 0;
    for (int i = 0; i <= r; ++i) ans += va[i];
    long long cur = ans;
    for (int l = 0; l < min(m, s / b); ++l) {
        cur += vb[l];
        sum += b;
        while (sum > s) {
            sum -= a;
            cur -= va[r--];
        }
        ans = max(ans, cur);
    }
    printf("%lld\n", ans);
    return 0;
}

Segment with the Required Subset

Code

#include <bits/stdc++.h>

using namespace std;

const int MAXM = 1005;

int n, m;
vector<int> v;

struct Stack{
    vector<int> v;
    vector<bitset<MAXM>> val;
    void init(int x) {
        bitset<MAXM> b = 0;
        b[x] = 1;
        val.push_back(b);
    }
    void push(int x, int t) {
        if (t) val.push_back(val.back() | val.back() << x);
        else val.push_back(val.back() | val.back() >> x);
        v.push_back(x);
    }
    int pop() {
        int x = v.back();
        val.pop_back();
        v.pop_back();
        return x;
    }
    bitset<MAXM> top() {
        return val.back();
    }
    bool empty() {
        return v.empty();
    }
} s1, s2;

void remove() {
    if (s1.empty()) {
        while (!s2.empty()) s1.push(s2.pop(), 1);
    }
    s1.pop();
}

int main() {
    scanf("%d%d", &n, &m);
    v.resize(n);
    for (auto &x : v) scanf("%d", &x);
    int l = 0, ans = n + 1;
    s1.init(0);
    s2.init(m);
    for (int r = 0; r < n; ++r) {
        s2.push(v[r], 0);
        while ((s1.top() & s2.top()).any()) {
            remove();
            ans = min(ans, r - l + 1);
            l++;
        }
    }
    if (ans > n) ans = -1;
    printf("%d\n", ans);
    return 0;
}

all you need to two pointer

→ Reply