# LeetCode 923: 3Sum With Multiplicity

## Problem Restatement

We are given an integer array `arr` and an integer `target`.

Return the number of index triples:

```python
i < j < k
```

such that:

```python
arr[i] + arr[j] + arr[k] == target
```

The array can contain duplicate values, and each valid index triple counts separately.

Because the answer can be large, return it modulo:

```python
10**9 + 7
```

The official problem asks for exactly this count of tuples `i, j, k` with `i < j < k`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `arr` and integer `target` |
| Output | Number of valid index triples |
| Index rule | `i < j < k` |
| Sum rule | `arr[i] + arr[j] + arr[k] == target` |
| Modulo | `10^9 + 7` |

Function shape:

```python
def threeSumMulti(arr: list[int], target: int) -> int:
    ...
```

## Examples

Example 1:

```python
arr = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
target = 8
```

Answer:

```python
20
```

The valid value combinations are:

| Values | Count |
|---|---:|
| `(1, 2, 5)` | `2 * 2 * 2 = 8` |
| `(1, 3, 4)` | `2 * 2 * 2 = 8` |
| `(2, 2, 4)` | `C(2, 2) * 2 = 2` |
| `(2, 3, 3)` | `2 * C(2, 2) = 2` |

Total:

```python
8 + 8 + 2 + 2 = 20
```

Example 2:

```python
arr = [1, 1, 2, 2, 2, 2]
target = 5
```

The only value pattern is:

```python
1 + 2 + 2 = 5
```

There are two `1` values and four `2` values.

Choose one `1` and two `2`s:

```python
2 * C(4, 2) = 2 * 6 = 12
```

Answer:

```python
12
```

These are the standard sample cases for this problem.

## First Thought: Check Every Triple

A direct solution is to try all triples of indices.

```python
class Solution:
    def threeSumMulti(self, arr: list[int], target: int) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        answer = 0

        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if arr[i] + arr[j] + arr[k] == target:
                        answer += 1

        return answer % MOD
```

This is correct, but it takes cubic time.

With `n` up to thousands, this is too slow.

## Key Insight

The values in `arr` are small in this problem. Common references list:

```python
0 <= arr[i] <= 100
```

and:

```python
0 <= target <= 300
```

So instead of iterating over indices, we can count how many times each value appears.

Then we enumerate possible values:

```python
x <= y <= z
```

where:

```python
x + y + z == target
```

For each value pattern, compute how many index triples it represents.

There are four cases:

| Case | Count |
|---|---:|
| `x < y < z` | `count[x] * count[y] * count[z]` |
| `x == y < z` | `C(count[x], 2) * count[z]` |
| `x < y == z` | `count[x] * C(count[y], 2)` |
| `x == y == z` | `C(count[x], 3)` |

## Combinations

We need:

```python
C(n, 2) = n * (n - 1) // 2
```

and:

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

These count how many ways to choose repeated values from their occurrences.

For example, if value `2` appears four times, then the number of ways to choose two `2`s is:

```python
C(4, 2) = 6
```

## Algorithm

1. Count the frequency of each value in `arr`.
2. Iterate `x` from `0` to `100`.
3. Iterate `y` from `x` to `100`.
4. Compute:

```python
z = target - x - y
```

5. Skip if `z < y` or `z > 100`.
6. Add the correct combinatorial count based on equality among `x`, `y`, and `z`.
7. Return the answer modulo `10^9 + 7`.

## Correctness

Every valid index triple has values:

```python
arr[i], arr[j], arr[k]
```

If we sort these three values conceptually, they form exactly one ordered value pattern:

```python
x <= y <= z
```

with:

```python
x + y + z == target
```

The algorithm enumerates every such pattern exactly once.

For each pattern, the combinatorial formula counts exactly how many index triples can be formed from the available occurrences.

If all three values are distinct, we choose one occurrence from each count.

If two values are equal, we choose two occurrences from that repeated value and one from the other value.

If all three values are equal, we choose three occurrences from that value.

These cases are disjoint and cover all possible triples.

Therefore, the algorithm counts every valid index triple exactly once and no invalid triple is counted.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(101^2 + n)` | Count the array, then enumerate value pairs |
| Space | `O(101)` | Frequencies for values `0` through `100` |

This is effectively linear in the input size.

## Implementation

```python
class Solution:
    def threeSumMulti(self, arr: list[int], target: int) -> int:
        MOD = 10**9 + 7

        count = [0] * 101

        for num in arr:
            count[num] += 1

        answer = 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:
                    continue

                if count[z] == 0:
                    continue

                if x < y < z:
                    answer += count[x] * count[y] * count[z]
                elif x == y < z:
                    answer += count[x] * (count[x] - 1) // 2 * count[z]
                elif x < y == z:
                    answer += count[x] * count[y] * (count[y] - 1) // 2
                else:
                    answer += count[x] * (count[x] - 1) * (count[x] - 2) // 6

        return answer % MOD
```

## Code Explanation

Create a frequency array:

```python
count = [0] * 101
```

Count every value:

```python
for num in arr:
    count[num] += 1
```

Enumerate value patterns with `x <= y`:

```python
for x in range(101):
    for y in range(x, 101):
```

Compute the needed third value:

```python
z = target - x - y
```

The condition:

```python
if z < y or z > 100:
    continue
```

keeps the order `x <= y <= z` and keeps `z` in range.

For three distinct values:

```python
answer += count[x] * count[y] * count[z]
```

For two equal first values:

```python
answer += count[x] * (count[x] - 1) // 2 * count[z]
```

For two equal last values:

```python
answer += count[x] * count[y] * (count[y] - 1) // 2
```

For all equal values:

```python
answer += count[x] * (count[x] - 1) * (count[x] - 2) // 6
```

Finally, return modulo:

```python
return answer % MOD
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.threeSumMulti(
        [1, 1, 2, 2, 3, 3, 4, 4, 5, 5],
        8,
    ) == 20

    assert s.threeSumMulti(
        [1, 1, 2, 2, 2, 2],
        5,
    ) == 12

    assert s.threeSumMulti(
        [0, 0, 0],
        0,
    ) == 1

    assert s.threeSumMulti(
        [0, 0, 0, 0],
        0,
    ) == 4

    assert s.threeSumMulti(
        [2, 2, 2, 2, 2],
        6,
    ) == 10

    assert s.threeSumMulti(
        [1, 2, 3, 4],
        9,
    ) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Main sample | Mixed distinct and repeated value patterns |
| `[1, 1, 2, 2, 2, 2]` | One value appears twice in the triple |
| `[0, 0, 0]` | Exactly one triple |
| Four zeros | Checks `C(4, 3)` |
| Five twos | Checks all-equal combination |
| `[1, 2, 3, 4]` | Distinct values only |