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 9Output
4Two 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.
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.
| i | j | a[i] + a[j] | Decision |
|---|---|---|---|
| 0 (1) | 6 (15) | 16 | > 13 → j-- |
| 0 (1) | 5 (11) | 12 | < 13 → i++ |
| 1 (2) | 5 (11) | 13 | the 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.
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).
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.
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.
Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.
We are given n numbers (1 ≤ n ≤ 105) and S. How many pairs i < j are there with a[i] + a[j] < S?
5 10
2 7 5 3 94We 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.
6 7
2 3 1 2 4 323 100
1 2 30i < j – the same element is not taken twice.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?