The Two Pointers Technique

Lesson 1 of 7 · Advanced techniques

Two indices that move through an array in the same or in opposite directions, and never go back. Many tasks that naively need two nested loops (O(n²)) are solved this way in one pass – in O(n) time.

Before you start: prior knowledge you need – the sort function (SR), binary search.
How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Pointers from both ends: a pair with a given sum

Task: in a sorted array find two elements whose sum is exactly S.

We put i at the beginning and j at the end of the array. If a[i] + a[j] is too small, the only way to make the sum grow is to move i to the right. If it is too large, we move j to the left. The pointers move towards each other, so there are at most n steps in total.

The array 1 2 4 7 8 11 15, S = 13
ija[i] + a[j]Decision
0 (1)6 (15)16> 13 → j--
0 (1)5 (11)12< 13 → i++
1 (2)5 (11)13the pair is found
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long S;
    cin >> n >> S;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;         // the array is sorted in ascending order

    int i = 0, j = n - 1;
    while (i < j) {
        long long sum = a[i] + a[j];
        if (sum == S) {
            cout << a[i] << " " << a[j] << endl;
            return 0;
        }
        if (sum < S) i++;               // we need a larger sum
        else j--;                       // we need a smaller sum
    }
    cout << "NONE" << endl;
    return 0;
}

For the input 7 13 / 1 2 4 7 8 11 15 the program prints 2 11.

A sliding window: the longest part with a sum of at most S

Task: we are given an array of non-negative numbers. Find the longest contiguous part whose sum is not greater than S.

We keep a "window" a[l..r] and its sum. We move the right end r and add the element; while the sum is too large, we remove the element at the left end (l++). Since the numbers are non-negative, shortening from the left always decreases the sum. Every element enters the window once and leaves it at most once – O(n) in total.

#include <iostream>
#include <vector>
using namespace std;

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

    long long sum = 0;
    int l = 0, longest = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];                    // a[r] enters the window
        while (sum > S) {               // the sum is too large: shorten from the left
            sum -= a[l];
            l++;
        }
        longest = max(longest, r - l + 1);
    }
    cout << longest << endl;
    return 0;
}

For the input 6 7 / 2 3 1 2 4 3 the program prints 3 (for example 2 + 3 + 1 = 6; every part of 4 elements has a sum greater than 7).

Two arrays at the same time

Merging two sorted arrays in merge sort is also a two pointers technique: one index in each array. In the same way, the common elements of two sorted arrays are found in O(n + m):

#include <iostream>
#include <vector>
using namespace std;

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

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] < b[j]) i++;
        else if (b[j] < a[i]) j++;
        else {                          // a common element
            cout << a[i] << " ";
            i++;
            j++;
        }
    }
    cout << endl;
    return 0;
}

For the arrays 1 3 5 7 9 and 2 3 4 7 10 the program prints 3 7.

When does it work?

The technique works when there is monotonicity: moving a pointer in one direction cannot miss a solution. For the pair with a sum this is guaranteed by the array being sorted, and for the window by the numbers being non-negative. If the array has negative numbers, the window does not work – then prefix sums help.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.

TASK 01Difficulty: medium

The number of pairs with a sum smaller than S

We are given n numbers (1 ≤ n ≤ 105) and S. How many pairs i < j are there with a[i] + a[j] < S?

Example

Input

5 10
2 7 5 3 9

Output

4
TASK 02Difficulty: medium

The shortest part with a sum of at least S

We are given an array of n positive numbers and a number S. Print the length of the shortest contiguous part whose sum is at least S, or 0 if there is no such part.

Example 1

Input

6 7
2 3 1 2 4 3

Output

2

Example 2

Input

3 100
1 2 3

Output

0
Common mistakes and tips
  • For a pair with a sum, the array must be sorted.
  • A window that is shortened from the left works only for non-negative numbers.
  • The loop condition for opposite pointers is i < j – the same element is not taken twice.

Check your knowledge

Open the quiz

The two pointers technique

1. The sum a[i] + a[j] is smaller than the one we are looking for. What do we move?




2. What is the complexity of the sliding window technique?




3. Why does the window not work when the array has negative numbers?