Practice › Hashing & Two Pointers
Pair Sum in a Sorted Array
Easy · Hashing & Two Pointers · Asked at Amazon, Microsoft, TCS, Infosys, Wipro
The array is sorted in non-decreasing order. Count the pairs of indices i < j with a[i] + a[j] = target.
Input
First line: n target. Second line: the sorted array.
Output
The number of pairs.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i], target ≤ 10^9
Two pointers from both ends. When the sum matches, count the run of equal values on each side (careful when both pointers are inside the same run).
Example 1
Input
5 6 1 2 3 4 5
Output
2
Example 2
Input
4 4 2 2 2 2
Output
6
Hints
- Start with pointers at both ends. If the sum is too small, move the left pointer right; if too big, move the right pointer left.
- When the sum matches, count how many copies of a[l] and of a[r] there are. If a[l] == a[r], all remaining elements are equal: there are c·(c−1)/2 pairs.
Approach
Two pointers l = 0, r = n−1. If a[l] + a[r] < target, advance l; if greater, retreat r. On a match with a[l] ≠ a[r], count the run cl of values equal to a[l] and the run cr equal to a[r]; they form cl · cr pairs; skip both runs. If a[l] == a[r], every element between them is that value, so add c(c−1)/2 with c = r − l + 1 and stop. Use 64-bit counts — up to ~5·10^9 pairs.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long t;
cin >> n >> t;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long cnt = 0;
int l = 0, r = n - 1;
while (l < r) {
long long s = a[l] + a[r];
if (s < t) l++;
else if (s > t) r--;
else if (a[l] == a[r]) {
long long c = r - l + 1;
cnt += c * (c - 1) / 2;
break;
} else {
long long cl = 1, cr = 1;
while (l + 1 < r && a[l + 1] == a[l]) l++, cl++;
while (r - 1 > l && a[r - 1] == a[r]) r--, cr++;
cnt += cl * cr;
l++;
r--;
}
}
cout << cnt << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, t, a = data[0], data[1], data[2:]
cnt, l, r = 0, 0, n - 1
while l < r:
s = a[l] + a[r]
if s < t:
l += 1
elif s > t:
r -= 1
elif a[l] == a[r]:
c = r - l + 1
cnt += c * (c - 1) // 2
break
else:
cl = cr = 1
while l + 1 < r and a[l + 1] == a[l]:
l += 1
cl += 1
while r - 1 > l and a[r - 1] == a[r]:
r -= 1
cr += 1
cnt += cl * cr
l += 1
r -= 1
print(cnt)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long t = sc.nextLong();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long cnt = 0;
int l = 0, r = n - 1;
while (l < r) {
long s = a[l] + a[r];
if (s < t) l++;
else if (s > t) r--;
else if (a[l] == a[r]) {
long c = r - l + 1;
cnt += c * (c - 1) / 2;
break;
} else {
long cl = 1, cr = 1;
while (l + 1 < r && a[l + 1] == a[l]) { l++; cl++; }
while (r - 1 > l && a[r - 1] == a[r]) { r--; cr++; }
cnt += cl * cr;
l++;
r--;
}
}
System.out.println(cnt);
}
}Solve Pair Sum in a Sorted Array online · All practice problems