Problem Description

The 3Sum With Multiplicity problem asks you to determine the number of triplets (i, j, k) in an array arr such that i < j < k and arr[i] + arr[j] + arr[k] == target. Unlike the classic 3Sum problem, elements in arr can have duplicates, and each valid combination of indices counts as a separate triplet. The answer should be returned modulo 10^9 + 7 to avoid large numbers.

• Input: An integer array arr (with possible duplicate values) and an integer target.
• Output: The number of triplets (i, j, k) such that i < j < k and arr[i] + arr[j] + arr[k] == target.
• Constraints:
  • 0 ≤ arr[i] ≤ 100
  • 3 ≤ arr.length ≤ 3000
  • 0 ≤ target ≤ 300
• Each element can be used multiple times (as long as their indices are different and in increasing order).

Thought Process

At first glance, the problem seems similar to the classic 3Sum, but with a twist: we care about the number of index-based combinations, not just unique values, and duplicates in the array matter. A brute-force approach would involve three nested loops to check every possible triplet, but this would be too slow for large arrays.

To optimize, we can notice that:

• All values are between 0 and 100, so we can count occurrences of each value efficiently.
• We can use combinatorics to count the number of ways to pick triplets with specific values, based on their counts.
• By fixing three values x, y, z (where x ≤ y ≤ z), and checking if x + y + z == target, we can calculate the number of valid index combinations for each case.

Solution Approach

We solve the problem efficiently using a frequency array and combinatorics. Here’s the step-by-step plan:

1. Count Frequency: Build an array count where count[x] is the number of times x appears in arr.
2. Iterate Over All Value Triplets: For all x from 0 to 100, y from x to 100, and z from y to 100:
   • Check if x + y + z == target.
   • If so, calculate the number of index triplets based on the counts of x, y, and z:
   • If all values are the same (x == y == z): Use count[x] choose 3.
   • If two values are the same (x == y != z or x != y == z): Use count[x] choose 2 * count[z] or count[x] * count[y] choose 2.
   • If all values are different: Use count[x] * count[y] * count[z].
3. Sum Up All Valid Combinations: Add up all the valid triplet counts, and return the result modulo 10^9 + 7.

We use a frequency array (hash map or fixed-size array) because the range of numbers is small, making lookups and combinations efficient. The combinatorics formulae are:

• C(n, 2) = n * (n - 1) / 2
• C(n, 3) = n * (n - 1) * (n - 2) / 6

Example Walkthrough

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8

• First, count the frequency of each number:
  • 1: 2 times, 2: 2 times, 3: 2 times, 4: 2 times, 5: 2 times
• Now, iterate over all x ≤ y ≤ z with x + y + z = 8:
  • 1 + 2 + 5 = 8: All different, so total = 2*2*2 = 8
  • 1 + 3 + 4 = 8: All different, so total = 2*2*2 = 8
  • 2 + 2 + 4 = 8: 2's are same, so total = C(2,2)*2 = 1*2 = 2
  • 2 + 3 + 3 = 8: 3's are same, so total = 2*C(2,2) = 2*1 = 2
• Add up all: 8 + 8 + 2 + 2 = 20

The answer is 20 triplets.

Time and Space Complexity

• Brute-force approach:
  • Three nested loops: O(N^3) time, where N is the length of arr.
  • Not feasible for N up to 3000.
• Optimized counting approach:
  • Counting frequencies: O(N)
  • Iterating over all triplets of values: Since values range from 0 to 100, at most 101*101*101 = 1,030,301 combinations (but we only check x ≤ y ≤ z, so much fewer).
  • Total time: O(N + M^3), where M = 101 (the range of values). This is very fast in practice.
  • Space: O(M) for the frequency array.

Summary

We solved the 3Sum With Multiplicity problem by leveraging the small range of possible values to count frequencies and use combinatorics, instead of brute-force enumeration. This approach is both efficient and elegant, using mathematical combinations to count valid index triplets. The key insight is to reduce the problem to counting value triplets and calculating the number of valid index combinations for each, making full use of the problem’s constraints.

Code Implementation

class Solution:
    def threeSumMulti(self, arr, target):
        MOD = 10 ** 9 + 7
        count = [0] * 101
        for num in arr:
            count[num] += 1
        ans = 0
        for x in range(101):
            if count[x] == 0:
                continue
            for y in range(x, 101):
                if count[y] == 0:
                    continue
                z = target - x - y
                if z < y or z > 100 or count[z] == 0:
                    continue
                if x == y == z:
                    ans += count[x] * (count[x] - 1) * (count[x] - 2) // 6
                elif x == y != z:
                    ans += count[x] * (count[x] - 1) // 2 * count[z]
                elif x < y and y == z:
                    ans += count[x] * count[y] * (count[y] - 1) // 2
                elif x < y < z:
                    ans += count[x] * count[y] * count[z]
                ans %= MOD
        return ans
      

class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        const int MOD = 1e9 + 7;
        vector<long long> count(101, 0);
        for (int num : arr) count[num]++;
        long long ans = 0;
        for (int x = 0; x <= 100; ++x) {
            if (count[x] == 0) continue;
            for (int y = x; y <= 100; ++y) {
                if (count[y] == 0) continue;
                int z = target - x - y;
                if (z < y || z > 100 || count[z] == 0) continue;
                if (x == y && y == z) {
                    ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
                } else if (x == y && y != z) {
                    ans += count[x] * (count[x] - 1) / 2 * count[z];
                } else if (x < y && y == z) {
                    ans += count[x] * count[y] * (count[y] - 1) / 2;
                } else if (x < y && y < z) {
                    ans += count[x] * count[y] * count[z];
                }
                ans %= MOD;
            }
        }
        return (int)ans;
    }
};
      

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        int MOD = 1_000_000_007;
        long[] count = new long[101];
        for (int num : arr) count[num]++;
        long ans = 0;
        for (int x = 0; x <= 100; x++) {
            if (count[x] == 0) continue;
            for (int y = x; y <= 100; y++) {
                if (count[y] == 0) continue;
                int z = target - x - y;
                if (z < y || z > 100 || count[z] == 0) continue;
                if (x == y && y == z) {
                    ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
                } else if (x == y && y != z) {
                    ans += count[x] * (count[x] - 1) / 2 * count[z];
                } else if (x < y && y == z) {
                    ans += count[x] * count[y] * (count[y] - 1) / 2;
                } else if (x < y && y < z) {
                    ans += count[x] * count[y] * count[z];
                }
                ans %= MOD;
            }
        }
        return (int)ans;
    }
}
      

var threeSumMulti = function(arr, target) {
    const MOD = 1e9 + 7;
    let count = new Array(101).fill(0);
    for (let num of arr) count[num]++;
    let ans = 0;
    for (let x = 0; x <= 100; x++) {
        if (count[x] === 0) continue;
        for (let y = x; y <= 100; y++) {
            if (count[y] === 0) continue;
            let z = target - x - y;
            if (z < y || z > 100 || count[z] === 0) continue;
            if (x === y && y === z) {
                ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
            } else if (x === y && y !== z) {
                ans += count[x] * (count[x] - 1) / 2 * count[z];
            } else if (x < y && y === z) {
                ans += count[x] * count[y] * (count[y] - 1) / 2;
            } else if (x < y && y < z) {
                ans += count[x] * count[y] * count[z];
            }
            ans %= MOD;
        }
    }
    return ans;
};