3Sum With Multiplicity

medium array hash map counting

Problem

Given arr and target, count tuples (i, j, k) with i < j < k and arr[i]+arr[j]+arr[k] = target. Return the count mod 10⁹ + 7.

Inputarr = [1,1,2,2,3,3,4,4,5,5], target = 8

Output20

Sum counts via combinatorics on distinct values (handle three cases: a=b=c, a=b<c, a<b<c).

arr (comma-separated)

target

from collections import Counter
def threeSumMulti(arr, target):
    MOD = 10**9 + 7
    cnt = Counter(arr)
    keys = sorted(cnt)
    total = 0
    for i, a in enumerate(keys):
        for j in range(i, len(keys)):
            b = keys[j]
            c = target - a - b
            if c < b or c not in cnt: continue
            if a == b == c:
                total += cnt[a] * (cnt[a] - 1) * (cnt[a] - 2) // 6
            elif a == b != c:
                total += cnt[a] * (cnt[a] - 1) // 2 * cnt[c]
            elif b == c != a:
                total += cnt[a] * cnt[b] * (cnt[b] - 1) // 2
            else:
                total += cnt[a] * cnt[b] * cnt[c]
            total %= MOD
    return total

function threeSumMulti(arr, target) {
  const MOD = 1_000_000_007;
  const cnt = new Map();
  for (const x of arr) cnt.set(x, (cnt.get(x) || 0) + 1);
  const keys = [...cnt.keys()].sort((a, b) => a - b);
  let total = 0;
  for (let i = 0; i < keys.length; i++) {
    for (let j = i; j < keys.length; j++) {
      const a = keys[i], b = keys[j], c = target - a - b;
      if (c < b || !cnt.has(c)) continue;
      const ca = cnt.get(a), cb = cnt.get(b), cc = cnt.get(c);
      let add;
      if (a === b && b === c) add = ca * (ca - 1) * (ca - 2) / 6;
      else if (a === b) add = ca * (ca - 1) / 2 * cc;
      else if (b === c) add = ca * cb * (cb - 1) / 2;
      else add = ca * cb * cc;
      total = (total + add) % MOD;
    }
  }
  return total;
}

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        final long MOD = 1_000_000_007L;
        long[] cnt = new long[101];
        for (int x : arr) cnt[x]++;
        long total = 0;
        for (int a = 0; a <= 100; a++) {
            if (cnt[a] == 0) continue;
            for (int b = a; b <= 100; b++) {
                if (cnt[b] == 0) continue;
                int c = target - a - b;
                if (c < b || c > 100 || cnt[c] == 0) continue;
                long add;
                if (a == b && b == c) add = cnt[a] * (cnt[a] - 1) * (cnt[a] - 2) / 6;
                else if (a == b) add = cnt[a] * (cnt[a] - 1) / 2 * cnt[c];
                else if (b == c) add = cnt[a] * cnt[b] * (cnt[b] - 1) / 2;
                else add = cnt[a] * cnt[b] * cnt[c];
                total = (total + add) % MOD;
            }
        }
        return (int)total;
    }
}

int threeSumMulti(vector<int>& arr, int target) {
    const long long MOD = 1000000007LL;
    long long cnt[101] = {0};
    for (int x : arr) cnt[x]++;
    long long total = 0;
    for (int a = 0; a <= 100; a++) {
        if (!cnt[a]) continue;
        for (int b = a; b <= 100; b++) {
            if (!cnt[b]) continue;
            int c = target - a - b;
            if (c < b || c > 100 || !cnt[c]) continue;
            long long add;
            if (a == b && b == c) add = cnt[a] * (cnt[a] - 1) * (cnt[a] - 2) / 6;
            else if (a == b) add = cnt[a] * (cnt[a] - 1) / 2 * cnt[c];
            else if (b == c) add = cnt[a] * cnt[b] * (cnt[b] - 1) / 2;
            else add = cnt[a] * cnt[b] * cnt[c];
            total = (total + add) % MOD;
        }
    }
    return (int)total;
}

Explanation

We count triplets (i, j, k) with i < j < k whose values sum to target. Instead of checking all triples of positions (too slow), we group by value using a frequency count and combine those counts with a little combinatorics.

We build cnt = how many times each value appears, sort the distinct values, and loop over pairs of values a <= b. The third value must be c = target - a - b; we only proceed if c >= b and c exists, which keeps each value-triple counted once.

Then we add the number of ways to actually pick positions, handling three cases. If a == b == c, the count is "choose 3 from cnt[a]" = cnt[a]*(cnt[a]-1)*(cnt[a]-2)/6. If exactly two values are equal, it's "choose 2" from that value times the count of the other. If all three values differ, it's just cnt[a]*cnt[b]*cnt[c].

Example: arr = [1,1,2,2,3,3,4,4,5,5], target = 8. Value-triples like (1,2,5), (1,3,4), (2,2,4), (3,3,2)… each contribute via these formulas, summing to 20.

Because there are few distinct values, looping over value pairs is far faster than over positions, and the combinatorics recovers the exact position counts.

Time: O(d²) where d = distinct values Space: O(d)