3Sum With Multiplicity

Medium
769.

3Sum With Multiplicity

3Sum With Multiplicity is a medium coding problem on arrays, hash table and two pointers, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function(arr, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

3Sum With Multiplicity — Solution in Python, Java & C++

3Sum With Multiplicity solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

3Sum With Multiplicity is a medium coding problem on arrays, hash table and two pointers, asked in Amazon, Google and Uber interviews.

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

Hints for 3Sum With Multiplicity

  1. Hint 1

    The values are tiny — at most 101 distinct ones — so count occurrences instead of scanning index triples.

  2. Hint 2

    Enumerate value pairs i <= j and derive k = target - i - j; skip it unless k >= j.

  3. Hint 3

    The three cases i = j = k, exactly two equal, and all distinct each have their own combination count.

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

  1. Tally cnt[v], how often each value appears.
  2. For every i <= j, set k = target - i - j and skip unless j <= k <= 300.
  3. 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].
  4. 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

Java

public static int threeSumMulti(int[] arr, int target) {
    final long MOD = 1000000007L;
    long[] cnt = new long[301];
    for (int x : arr) cnt[x]++;
    long res = 0;
    for (int i = 0; i <= 300; i++) {
        if (cnt[i] == 0) continue;
        for (int j = i; j <= 300; j++) {
            if (cnt[j] == 0) continue;
            int k = target - i - j;
            if (k < j || k > 300 || cnt[k] == 0) continue;
            long 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 (int) res;
}

C++

int threeSumMulti(vector<int>& arr, int target) {
    const long long MOD = 1000000007LL;
    vector<long long> cnt(301, 0);
    for (int x : arr) cnt[x]++;
    long long res = 0;
    for (int i = 0; i <= 300; i++) {
        if (cnt[i] == 0) continue;
        for (int j = i; j <= 300; j++) {
            if (cnt[j] == 0) continue;
            int k = target - i - j;
            if (k < j || k > 300 || cnt[k] == 0) continue;
            long long 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 (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets