3Sum With Multiplicity — Medium Problem & Solution

Count the index triples i < j < k with arr[i] + arr[j] + arr[k] == target. Because the count can be huge, return it modulo 10^9 + 7.

Difficulty: Medium
Topics: Arrays, Hash Table, Two Pointers, Counting
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Count the index triples i < j < k with arr[i] + arr[j] + arr[k] == target.

Because the count can be huge, return it modulo 10^9 + 7.

Example 1

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: The value patterns are (1,2,5), (1,3,4), (2,2,4) and (2,3,3).

Example 2

Input: arr = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: Choosing one 1 and two 2s: 2 · C(4,2) = 12.

Example 3

Input: arr = [0,0,0], target = 0
Output: 1

Constraints

3 <= arr.length <= 3000
0 <= arr[i] <= 100
0 <= target <= 300

How to solve 3Sum With Multiplicity

With only 101 possible values, counting by value collapses the O(n³) triple enumeration to a loop over value pairs. For each ordered value triple i <= j <= k the number of index triples is a small combinatorial formula over the occurrence counts.

Approach

Tally cnt[v], how often each value appears.
For every i <= j, set k = target - i - j and skip unless j <= k <= 300.
All three equal: C(cnt[i], 3). Exactly i = j: C(cnt[i], 2) · cnt[k]. Exactly j = k: cnt[i] · C(cnt[j], 2). All distinct: cnt[i] · cnt[j] · cnt[k].
Sum modulo 10^9 + 7.

Why it works

Every index triple i < j < k has exactly one sorted value triple, and requiring i <= j <= k in the enumeration counts each value pattern once. Within a pattern, choosing which indices carry each value is a product of binomial coefficients — a combination when a value is used more than once, a plain count otherwise.

Complexity

Time — O(n + V²) where V = 101
Space — O(V)

Pitfalls

Enumerating unordered pairs without the k >= j guard counts each pattern several times.
Using cnt[i] · cnt[j] · cnt[k] when two values coincide over-counts — the same index would be reused.
The intermediate products reach about 3000³ / 6 ≈ 4.5 · 10^9, so accumulate in 64-bit and reduce.

Reference solution

Python

from typing import List

def threeSumMulti(arr: List[int], target: int) -> int:
    MOD = 1000000007
    cnt = [0] * 301
    for x in arr:
        cnt[x] += 1
    res = 0
    for i in range(301):
        for j in range(i, 301):
            k = target - i - j
            if k < j or k > 300:
                continue
            if cnt[i] == 0 or cnt[j] == 0 or cnt[k] == 0:
                continue
            if i == j == k:
                ways = cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) // 6
            elif i == j:
                ways = cnt[i] * (cnt[i] - 1) // 2 * cnt[k]
            elif j == k:
                ways = cnt[i] * (cnt[j] * (cnt[j] - 1) // 2)
            else:
                ways = cnt[i] * cnt[j] * cnt[k]
            res = (res + ways) % MOD
    return res

JavaScript

var threeSumMulti = function(arr, target) {
    var MOD = 1000000007;
    var cnt = [];
    for (var t = 0; t <= 300; t++) cnt.push(0);
    for (var a = 0; a < arr.length; a++) cnt[arr[a]]++;
    var res = 0;
    for (var i = 0; i <= 300; i++) {
        if (cnt[i] === 0) continue;
        for (var j = i; j <= 300; j++) {
            if (cnt[j] === 0) continue;
            var k = target - i - j;
            if (k < j || k > 300 || cnt[k] === 0) continue;
            var ways;
            if (i === j && j === k) ways = cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;
            else if (i === j) ways = (cnt[i] * (cnt[i] - 1) / 2) * cnt[k];
            else if (j === k) ways = cnt[i] * (cnt[j] * (cnt[j] - 1) / 2);
            else ways = cnt[i] * cnt[j] * cnt[k];
            res = (res + ways) % MOD;
        }
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue