LeetCode 923: 3Sum With Multiplicity

Problem Restatement

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

Return the number of index triples:

i < j < k

such that:

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:

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:

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

Examples

Example 1:

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

Answer:

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:

8 + 8 + 2 + 2 = 20

Example 2:

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

The only value pattern is:

1 + 2 + 2 = 5

There are two 1 values and four 2 values.

Choose one 1 and two 2s:

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

Answer:

These are the standard sample cases for this problem.

First Thought: Check Every Triple

A direct solution is to try all triples of indices.

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:

0 <= arr[i] <= 100

and:

0 <= target <= 300

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

Then we enumerate possible values:

x <= y <= z

where:

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:

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

and:

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 2s is:

C(4, 2) = 6

Algorithm

Count the frequency of each value in arr.
Iterate x from 0 to 100.
Iterate y from x to 100.
Compute:

z = target - x - y

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

Correctness

Every valid index triple has values:

arr[i], arr[j], arr[k]

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

x <= y <= z

with:

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

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:

count = [0] * 101

Count every value:

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

Enumerate value patterns with x <= y:

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

Compute the needed third value:

z = target - x - y

The condition:

if z < y or z > 100:
    continue

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

For three distinct values:

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

For two equal first values:

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

For two equal last values:

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

For all equal values:

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

Finally, return modulo:

return answer % MOD

Testing

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