Practice › Arrays
3Sum Count
Medium · Arrays · Asked at Amazon, Google, Microsoft, Adobe, Meta
Count the number of unique triplets of values (a, b, c) taken from three different positions such that a + b + c = 0. Triplets with the same values (in any order) count once.
Input
First line: n. Second line: n space-separated integers.
Output
The number of unique zero-sum triplets.
Constraints
- 3 ≤ n ≤ 3000
- -10^5 ≤ a[i] ≤ 10^5
Sort, fix one element, then use two pointers and skip duplicates — O(n²).
Example 1
Input
6 -1 0 1 2 -1 -4
Output
2
Example 2
Input
3 0 1 1
Output
0
Hints
- Sort the array first. Fix the smallest element a[i]; now you need two numbers summing to −a[i].
- Find those with two pointers from both ends, skipping equal values so each value triplet counts once.
Approach
Sort. For each i (skipping a[i] equal to a[i-1]), put lo = i + 1 and hi = n − 1. If a[i] + a[lo] + a[hi] is too small move lo right, if too big move hi left. When it equals 0, count one triplet, then move both pointers past every copy of their current values. Skipping duplicates at all three positions is what makes each value triplet count once.
Complexity: O(n²) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long count = 0;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
int lo = i + 1, hi = n - 1;
while (lo < hi) {
long long s = a[i] + a[lo] + a[hi];
if (s < 0) lo++;
else if (s > 0) hi--;
else {
count++;
long long L = a[lo], H = a[hi];
while (lo < hi && a[lo] == L) lo++;
while (lo < hi && a[hi] == H) hi--;
}
}
}
cout << count << "\n";
return 0;
}Python solution
import sys
from collections import Counter
data = list(map(int, sys.stdin.read().split()))
cnt = Counter(data[1 : data[0] + 1])
vals = sorted(cnt)
present = set(vals)
count = 0
# choose values x <= y <= z with x + y + z = 0, checking we have enough copies of each
for i, x in enumerate(vals):
if x > 0:
break
for y in vals[i:]:
z = -x - y
if z < y:
break
if z not in present:
continue
need = Counter((x, y, z))
if all(cnt[v] >= c for v, c in need.items()):
count += 1
print(count)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[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
Arrays.sort(a);
long count = 0;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
int lo = i + 1, hi = n - 1;
while (lo < hi) {
long s = a[i] + a[lo] + a[hi];
if (s < 0) lo++;
else if (s > 0) hi--;
else {
count++;
long L = a[lo], H = a[hi];
while (lo < hi && a[lo] == L) lo++;
while (lo < hi && a[hi] == H) hi--;
}
}
}
System.out.println(count);
}
}