LeetCode 923 - 3Sum With Multiplicity

LeetCode Problem 923

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, Sorting, Counting

Solution

Problem Understanding

The problem asks us to count how many index triplets (i, j, k) satisfy two conditions:

• The indices must follow the order i < j < k
• The values at those indices must sum to the given target

Formally, we want:

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

The important detail is that we are counting tuples of indices, not unique value combinations. If the same values appear multiple times in the array, each valid index combination must be counted separately.

For example, if the array contains several 2s and several 3s, every distinct choice of indices contributes to the answer.

The input consists of:

• arr, an integer array
• target, the required sum

The output is the number of valid triplets modulo 10^9 + 7.

The constraints are especially important here:

• arr.length <= 3000
• arr[i] <= 100
• target <= 300

The array size is large enough that an O(n^3) brute-force solution is too slow. However, the values themselves are very small, only ranging from 0 to 100. That observation opens the door for counting-based optimizations.

There are several edge cases that can easily introduce bugs:

• Arrays with many duplicate values
• Situations where all three chosen numbers are identical
• Situations where exactly two numbers are identical
• Large counts that require modulo arithmetic
• Arrays where many combinations produce the same sum

The problem guarantees:

• At least three elements exist
• All values are non-negative integers
• The answer fits within normal integer arithmetic before applying modulo in Python, but modulo is still required by the problem statement

Approaches

Brute Force Approach

The most direct solution is to try every possible triplet (i, j, k) where i < j < k.

We can use three nested loops:

• The first loop chooses i
• The second loop chooses j
• The third loop chooses k

For each triplet, we compute the sum and check whether it equals target. If it does, we increment the answer.

This approach is correct because it explicitly examines every valid index combination exactly once.

However, the complexity is too high. With n = 3000, the number of triplets is approximately:

3000^3 = 27,000,000,000

That is far beyond acceptable runtime limits.

Key Insight for the Optimal Solution

The crucial observation is that the array values are very small:

0 <= arr[i] <= 100

Instead of focusing on indices directly, we can count how many times each value appears.

Once we know the frequency of every number, we can iterate over value combinations instead of index combinations.

There are only 101 possible values, from 0 to 100.

We can try all combinations (x, y, z) such that:

x + y + z == target

Then we compute how many index triplets those values generate.

This transforms the problem from iterating over up to billions of index combinations into iterating over a very small value space.

The main challenge becomes correctly counting combinations when:

• All three values are different
• Two values are equal
• All three values are equal

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triplet directly
Optimal	O(101²)	O(101)	Uses frequency counting and combinatorics

Algorithm Walkthrough

1. Create a frequency array or hash map to count how many times each number appears in arr.

Since values only range from 0 to 100, we can use a fixed-size array of length 101. 2. Initialize the answer variable to 0. 3. Iterate through all possible values x from 0 to 100. 4. For each x, iterate through all possible values y from x to 100.

Starting y from x ensures we avoid duplicate permutations. 5. Compute the required third value:

z = target - x - y

6. Skip invalid cases:

• If z < y, skip it because we maintain the ordering x <= y <= z
• If z > 100, skip it because values are bounded

7. Now determine how many triplets this value combination contributes.

There are four distinct cases:

• Case 1: x == y == z

We need to choose any 3 indices from the occurrences of x.

The count is:

$\binom{count[x]}{3}$

• Case 2: x == y != z

We choose 2 copies of x and 1 copy of z.

The count is:

$\binom{count[x]}{2} \cdot count[z]$

• Case 3: x != y == z

We choose 1 copy of x and 2 copies of y.

The count is:

$count[x] \cdot \binom{count[y]}{2}$

• Case 4: x < y < z

All values are different.

The count is:

$count[x] \cdot count[y] \cdot count[z]$ 8. Add the computed contribution to the answer. 9. Return the answer modulo 10^9 + 7.

Why it works

The algorithm works because every valid triplet of indices corresponds to exactly one ordered value combination satisfying:

x <= y <= z

By enforcing this ordering, we avoid double counting.

The combinatorial formulas correctly count how many index selections exist for each value pattern:

• Choosing 3 identical values
• Choosing 2 identical values
• Choosing 3 distinct values

Since all possible value combinations are examined, every valid triplet is counted exactly once.

Python Solution

from typing import List

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):
            for y in range(x, 101):
                z = target - x - y
                
                if z < y or z > 100:
                    continue
                
                if x == y == z:
                    n = count[x]
                    answer += n * (n - 1) * (n - 2) // 6
                
                elif x == y != z:
                    n = count[x]
                    answer += (n * (n - 1) // 2) * count[z]
                
                elif x < y and y == z:
                    n = count[y]
                    answer += count[x] * (n * (n - 1) // 2)
                
                else:
                    answer += count[x] * count[y] * count[z]
        
        return answer % MOD

The implementation begins by counting the frequency of every value in the array. Because values only range from 0 to 100, a fixed-size list is more efficient than a dictionary.

The nested loops iterate over all valid ordered pairs (x, y). For each pair, the required third value z is computed directly from the target.

The condition:

if z < y or z > 100:

ensures that:

• We maintain the ordering x <= y <= z
• The third value remains within valid bounds

The four combinatorial cases are handled separately because each requires a different counting formula.

For identical values, combinations are computed using standard combinatorics formulas:

• Choosing 2 items from n
• Choosing 3 items from n

Finally, the answer is returned modulo 10^9 + 7.

Go Solution

func threeSumMulti(arr []int, target int) int {
    const MOD int = 1000000007

    count := make([]int, 101)

    for _, num := range arr {
        count[num]++
    }

    answer := 0

    for x := 0; x <= 100; x++ {
        for y := x; y <= 100; y++ {
            z := target - x - y

            if z < y || z > 100 {
                continue
            }

            if x == y && y == z {
                n := count[x]
                answer += n * (n - 1) * (n - 2) / 6

            } else if x == y && y != z {
                n := count[x]
                answer += (n * (n - 1) / 2) * count[z]

            } else if x < y && y == z {
                n := count[y]
                answer += count[x] * (n * (n - 1) / 2)

            } else {
                answer += count[x] * count[y] * count[z]
            }

            answer %= MOD
        }
    }

    return answer
}

The Go implementation follows the same logic as the Python version.

A fixed-size slice of length 101 is used for frequency counting. Since Go uses explicit integer types, modulo reduction is applied during accumulation to avoid unnecessary growth.

Unlike Python, Go does not automatically support arbitrarily large integers, but the values in this problem remain safely within normal integer limits.

Worked Examples

Example 1

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

Frequency table:

Value	Count
1	2
2	2
3	2
4	2
5	2

Valid combinations:

x	y	z	Case	Contribution
1	2	5	all distinct	2 × 2 × 2 = 8
1	3	4	all distinct	2 × 2 × 2 = 8
2	2	4	x == y	C(2,2) × 2 = 2
2	3	3	y == z	2 × C(2,2) = 2

Total:

8 + 8 + 2 + 2 = 20

Example 2

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

Frequency table:

Value	Count
1	2
2	4

The only valid combination is:

x	y	z	Case	Contribution
1	2	2	y == z	2 × C(4,2)

Compute:

$2 \times \binom{4}{2} = 2 \times 6 = 12$

Final answer:

12

Example 3

arr = [2,1,3]
target = 6

Frequency table:

Value	Count
1	1
2	1
3	1

Valid combination:

x	y	z	Contribution
1	2	3	1 × 1 × 1 = 1

Final answer:

1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(101²)	Iterates over all possible value pairs
Space	O(101)	Frequency array for values 0 through 100

The complexity is effectively constant relative to input size because the value range is fixed.

The nested loops iterate at most:

101 × 101 = 10201

iterations, which is extremely efficient.

The frequency array also has fixed size, so memory usage remains constant.

Test Cases

sol = Solution()

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

# Example 2
assert sol.threeSumMulti(
    [1,1,2,2,2,2], 5
) == 12

# Example 3
assert sol.threeSumMulti(
    [2,1,3], 6
) == 1

# All elements identical
assert sol.threeSumMulti(
    [2,2,2,2], 6
) == 4  # C(4,3)

# No valid triplets
assert sol.threeSumMulti(
    [1,2,3], 100
) == 0

# Large duplicate counts
assert sol.threeSumMulti(
    [0] * 100, 0
) == 161700  # C(100,3)

# Mixed duplicates
assert sol.threeSumMulti(
    [1,1,1,2,2,2,3,3,3], 6
) == 28

# Minimum array size
assert sol.threeSumMulti(
    [1,2,3], 6
) == 1

# Target achievable with repeated values
assert sol.threeSumMulti(
    [0,0,0,1,1], 0
) == 1

# Multiple overlapping combinations
assert sol.threeSumMulti(
    [0,1,2,2,2,3,3], 6
) == 10

Test Summary

Test	Why
[1,1,2,2,3,3,4,4,5,5]	Standard mixed duplicate scenario
[1,1,2,2,2,2]	Tests two-equal-value combinatorics
[2,1,3]	Smallest non-trivial valid input
[2,2,2,2]	Tests all-three-equal counting
[1,2,3] with target 100	Ensures zero-result handling
[0] * 100	Stress test with huge combination count
Mixed duplicates totaling 6	Validates multiple counting paths
Minimum length array	Boundary condition
[0,0,0,1,1]	Tests exact triple selection
Overlapping combinations	Ensures no double counting

Edge Cases

One important edge case occurs when all three chosen values are identical. For example:

arr = [2,2,2,2]
target = 6

A naive implementation may incorrectly count permutations or fail to use combinatorics properly. The correct answer comes from choosing any 3 indices out of 4 occurrences. The implementation handles this using the combination formula:

$\binom{n}{3}$

Another tricky edge case occurs when exactly two values are equal. For example:

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

The algorithm must distinguish between:

• x == y != z
• x != y == z

These cases require different formulas. Treating them identically would produce incorrect counts or double counting.

A third important edge case involves large duplicate frequencies. Consider:

arr = [0] * 3000
target = 0

The number of valid triplets becomes extremely large. Without modulo arithmetic, some languages could overflow integer limits. The implementation applies modulo operations to ensure the result remains within bounds.

Another subtle case occurs when no valid triplets exist. For example:

arr = [1,2,3]
target = 100

The algorithm correctly skips impossible value combinations because z either falls outside the valid range or does not exist in the frequency table.