Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Sort the array first. Fix the smallest element a[i]; now you need two numbers summing to −a[i].
  2. 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);
    }
}

Solve 3Sum Count online · All practice problems