# 3Sum With Multiplicity
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/3sum-with-multiplicity)
Canonical: https://scaleengineer.com/dsa/problems/3sum-with-multiplicity
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
Given an integer array `arr`, and an integer `target`, return the number of tuples `i, j, k` such that `i < j < k` and `arr[i] + arr[j] + arr[k] == target`.

As the answer can be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** arr = [1,1,2,2,3,3,4,4,5,5], target = 8
**Output:** 20
**Explanation:** 
Enumerating by the values (arr[i], arr[j], arr[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

**Example 2:**

**Input:** arr = [1,1,2,2,2,2], target = 5
**Output:** 12
**Explanation:** 
arr[i] = 1, arr[j] = arr[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

**Example 3:**

**Input:** arr = [2,1,3], target = 6
**Output:** 1
**Explanation:** (1, 2, 3) occured one time in the array so we return 1.

**Constraints:**

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

# Approaches
## Brute Force
This is the most straightforward and intuitive approach. It involves checking every possible combination of three distinct elements from the array to see if they sum up to the target. We use three nested loops to generate all triplets of indices `(i, j, k)` with the condition `i < j < k` and sum the corresponding elements.
**Time:** O(N³), where N is the length of the array `arr`. With N up to 3000, this is approximately 2.7 * 10¹⁰ operations, which is too slow. · **Space:** O(1) - We only use a few variables for loops and the counter, so the space required is constant.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Extremely inefficient for the given constraints.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms.
### Explanation
The algorithm iterates through every unique triplet of indices `(i, j, k)`. For each triplet, it calculates the sum `arr[i] + arr[j] + arr[k]` and compares it with the `target`. If they are equal, a counter is incremented. This process guarantees that all valid combinations are found. However, its cubic time complexity makes it impractical for an array size of up to 3000.

```java
class Solution {
    public int threeSumMulti(int[] arr, int target) {
        long ans = 0;
        int n = arr.length;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (arr[i] + arr[j] + arr[k] == target) {
                        ans++;
                    }
                }
            }
        }
        return (int)(ans % MOD);
    }
}
```
### Algorithm
1. Initialize a `long` counter `ans` to 0 and `MOD = 1_000_000_007`.
2. Get the length of the array, `n`.
3. Use three nested loops to iterate through all possible triplets of indices `(i, j, k)` such that `i < j < k`.
   - The outer loop for `i` runs from `0` to `n - 3`.
   - The middle loop for `j` runs from `i + 1` to `n - 2`.
   - The inner loop for `k` runs from `j + 1` to `n - 1`.
4. Inside the innermost loop, check if the sum of elements at these indices equals the target: `arr[i] + arr[j] + arr[k] == target`.
5. If the condition is true, increment the `ans` counter.
6. After the loops complete, return `ans` modulo `MOD`.

## Sorting with Two Pointers
A significant improvement over the brute-force approach is to first sort the array. After sorting, we can iterate through the array to fix the first element of the triplet, `arr[i]`. For the remaining part of the array, we use a two-pointer technique to find pairs `(arr[j], arr[k])` that sum up to `target - arr[i]`. The main challenge here is to correctly count the combinations when duplicate numbers are present.
**Time:** O(N²). The sorting step takes O(N log N), and the nested loops (the outer for-loop and the inner two-pointer while-loop) take O(N²) time. The overall complexity is dominated by the O(N²) part. · **Space:** O(log N) or O(N), depending on the space used by the sorting algorithm.
**Pros:** Much more efficient than the brute-force approach.; A common and powerful pattern for solving k-sum problems.
**Cons:** Not the most optimal solution for this specific problem due to the small range of element values.; The logic to handle duplicate elements can be tricky to implement correctly.
### Explanation
By sorting the array, we can efficiently search for the other two numbers. For each `arr[i]`, we search for two numbers in the subarray `arr[i+1...n-1]` that sum to `target - arr[i]`. The two-pointer approach works because the subarray is sorted. When we find a valid pair `(arr[j], arr[k])`, we must account for all occurrences of `arr[j]` and `arr[k]` to get the correct multiplicity. If `arr[j]` and `arr[k]` are different, we count their frequencies and multiply. If they are the same, we use the combination formula `nC2` to count the pairs.

```java
import java.util.Arrays;

class Solution {
    public int threeSumMulti(int[] arr, int target) {
        int MOD = 1_000_000_007;
        long ans = 0;
        int n = arr.length;
        Arrays.sort(arr);

        for (int i = 0; i < n; ++i) {
            int T = target - arr[i];
            int j = i + 1, k = n - 1;

            while (j < k) {
                if (arr[j] + arr[k] < T) {
                    j++;
                } else if (arr[j] + arr[k] > T) {
                    k--;
                } else { // arr[j] + arr[k] == T
                    if (arr[j] != arr[k]) {
                        int leftCount = 1;
                        while (j + 1 < k && arr[j] == arr[j + 1]) {
                            leftCount++;
                            j++;
                        }
                        int rightCount = 1;
                        while (k - 1 > j && arr[k] == arr[k - 1]) {
                            rightCount++;
                            k--;
                        }
                        ans += (long) leftCount * rightCount;
                        ans %= MOD;
                        j++;
                        k--;
                    } else { // arr[j] == arr[k]
                        long m = k - j + 1;
                        ans += (m * (m - 1) / 2);
                        ans %= MOD;
                        break;
                    }
                }
            }
        }
        return (int) ans;
    }
}
```
### Algorithm
1. Define `MOD = 1_000_000_007` and initialize a `long` counter `ans` to 0.
2. Sort the input array `arr`.
3. Iterate through the array with a for-loop for the first element, `arr[i]`, from `i = 0` to `n - 1`.
4. For each `arr[i]`, set up two pointers, `j = i + 1` and `k = n - 1`.
5. Calculate the required sum for the pair: `T = target - arr[i]`.
6. While `j < k`:
   - If `arr[j] + arr[k] < T`, increment `j` to get a larger sum.
   - If `arr[j] + arr[k] > T`, decrement `k` to get a smaller sum.
   - If `arr[j] + arr[k] == T`, we have found a valid triplet. Now, handle duplicates:
     - **Case 1: `arr[j] != arr[k]`**: Count the number of consecutive duplicates for `arr[j]` (let's say `leftCount`) and `arr[k]` (`rightCount`). The number of new combinations is `leftCount * rightCount`. Add this to `ans`. Move `j` forward by `leftCount` and `k` backward by `rightCount`.
     - **Case 2: `arr[j] == arr[k]`**: All elements between `j` and `k` are identical. The number of elements is `m = k - j + 1`. We need to choose 2 from these `m` elements, which is `m * (m - 1) / 2`. Add this to `ans` and break the inner while loop, as all other pairs within this range have been counted.
7. After each addition to `ans`, take the result modulo `MOD`.
8. Return the final `ans`.

## Counting Frequencies with Combinatorics
This approach leverages the problem's constraint that the values in `arr` are limited to the range [0, 100]. Instead of iterating through the array indices, we can iterate through the possible values. First, we count the frequency of each number. Then, we consider all unique triplets of values `(x, y, z)` that sum to the `target`. For each such value-triplet, we use combinatorics to calculate how many ways we can form it using the numbers available in the input array.
**Time:** O(N + V²), where N is the length of `arr` and V is the range of values (101). The first step, counting frequencies, takes O(N). The second step, iterating through value combinations, takes O(V²). Given N <= 3000 and V = 101, this is much faster than O(N²). · **Space:** O(V), where V is the range of values in `arr`. Since V is 101, this is effectively O(1) constant space.
**Pros:** The most efficient approach for the given constraints.; Avoids the O(N²) complexity of iterating through the array.
**Cons:** The logic is more complex due to handling different combinatorial cases.; This approach is only highly effective when the range of values in the array is small compared to its length.
### Explanation
The core idea is to shift from an index-based search to a value-based search. We pre-calculate the frequency of each number from 0 to 100. Then, we iterate through all combinations of values `x`, `y`, and `z` such that `x + y + z = target` and `x <= y <= z`. The condition `x <= y <= z` prevents us from counting the same set of values multiple times (e.g., (1, 2, 5) and (2, 1, 5)). Based on whether `x`, `y`, and `z` are distinct or not, we apply the appropriate combination formula using their frequencies.

```java
class Solution {
    public int threeSumMulti(int[] arr, int target) {
        int MOD = 1_000_000_007;
        long[] counts = new long[101];
        for (int num : arr) {
            counts[num]++;
        }

        long ans = 0;

        for (int x = 0; x <= 100; x++) {
            for (int y = x; y <= 100; y++) {
                int z = target - x - y;
                if (z < y || z > 100) {
                    continue;
                }
                
                if (counts[x] == 0 || counts[y] == 0 || counts[z] == 0) {
                    continue;
                }

                if (x == y && y == z) { // Case: x = y = z
                    ans += (counts[x] * (counts[x] - 1) * (counts[x] - 2) / 6);
                } else if (x == y) { // Case: x = y != z
                    ans += (counts[x] * (counts[x] - 1) / 2) * counts[z];
                } else if (y == z) { // Case: x < y = z
                    ans += counts[x] * (counts[y] * (counts[y] - 1) / 2);
                } else { // Case: x < y < z
                    ans += counts[x] * counts[y] * counts[z];
                }
                ans %= MOD;
            }
        }
        return (int) ans;
    }
}
```
### Algorithm
1. Define `MOD = 1_000_000_007` and initialize a `long` counter `ans` to 0.
2. Create a frequency map (an array `counts` of size 101, since values are 0-100) to store the counts of each number in `arr`.
3. Iterate through `arr` once to populate the `counts` array.
4. Iterate through all possible unique value triplets `(x, y, z)` that sum to the target. To avoid overcounting, ensure `x <= y <= z`.
   - Loop `x` from `0` to `100`.
   - Loop `y` from `x` to `100`.
   - Calculate `z = target - x - y`.
   - If `z` is out of the valid range (`z < y` or `z > 100`), continue to the next iteration.
5. If `counts[x]`, `counts[y]`, or `counts[z]` is zero, this triplet cannot be formed, so continue.
6. Calculate the number of combinations based on the values of `x`, `y`, and `z`:
   - **Case 1: `x == y == z`**: We need to choose 3 items from `counts[x]`. The number of ways is `C(counts[x], 3) = counts[x] * (counts[x] - 1) * (counts[x] - 2) / 6`.
   - **Case 2: `x == y != z`**: Choose 2 from `counts[x]` and 1 from `counts[z]`. Ways: `C(counts[x], 2) * counts[z]`.
   - **Case 3: `x < y == z`**: Choose 1 from `counts[x]` and 2 from `counts[y]`. Ways: `counts[x] * C(counts[y], 2)`.
   - **Case 4: `x < y < z`**: Choose 1 from each. Ways: `counts[x] * counts[y] * counts[z]`.
7. Add the calculated combinations to `ans`, taking the modulo `MOD` at each step.
8. Return the final `ans`.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int threeSumMulti(int[] arr, int target) {
    int[] cnt = new int[101];
    for (int v : arr) {
      ++cnt[v];
    }
    long ans = 0;
    for (int j = 0; j < arr.length; ++j) {
      int b = arr[j];
      --cnt[b];
      for (int i = 0; i < j; ++i) {
        int a = arr[i];
        int c = target - a - b;
        if (c >= 0 && c <= 100) {
          ans = (ans + cnt[c]) % MOD;
        }
      }
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int threeSumMulti(vector<int> &arr, int target) {
    int cnt[101] = {0};
    for (int &v : arr) {
      ++cnt[v];
    }
    long ans = 0;
    for (int j = 0; j < arr.size(); ++j) {
      int b = arr[j];
      --cnt[b];
      for (int i = 0; i < j; ++i) {
        int a = arr[i];
        int c = target - a - b;
        if (c >= 0 && c <= 100) {
          ans += cnt[c];
          ans %= mod;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def threeSumMulti(self, arr: List[int], target: int) -> int: cnt = Counter(arr) ans = 0 mod = 10 ** 9 + 7 for j, b in enumerate(arr): cnt[b] -= 1 for i in range(j): a = arr[i] c = target - a - b ans = (ans + cnt[c]) % mod return ans

```