3Sum With Multiplicity
MedPrompt
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 <= 30000 <= arr[i] <= 1000 <= target <= 300
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a
longcounteransto 0 andMOD = 1_000_000_007. - Get the length of the array,
n. - Use three nested loops to iterate through all possible triplets of indices
(i, j, k)such thati < j < k.- The outer loop for
iruns from0ton - 3. - The middle loop for
jruns fromi + 1ton - 2. - The inner loop for
kruns fromj + 1ton - 1.
- The outer loop for
- Inside the innermost loop, check if the sum of elements at these indices equals the target:
arr[i] + arr[j] + arr[k] == target. - If the condition is true, increment the
anscounter. - After the loops complete, return
ansmoduloMOD.
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Define
MOD = 1_000_000_007and initialize alongcounteransto 0. - Sort the input array
arr. - Iterate through the array with a for-loop for the first element,
arr[i], fromi = 0ton - 1. - For each
arr[i], set up two pointers,j = i + 1andk = n - 1. - Calculate the required sum for the pair:
T = target - arr[i]. - While
j < k:- If
arr[j] + arr[k] < T, incrementjto get a larger sum. - If
arr[j] + arr[k] > T, decrementkto 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 forarr[j](let's sayleftCount) andarr[k](rightCount). The number of new combinations isleftCount * rightCount. Add this toans. Movejforward byleftCountandkbackward byrightCount. - Case 2:
arr[j] == arr[k]: All elements betweenjandkare identical. The number of elements ism = k - j + 1. We need to choose 2 from thesemelements, which ism * (m - 1) / 2. Add this toansand break the inner while loop, as all other pairs within this range have been counted.
- Case 1:
- If
- After each addition to
ans, take the result moduloMOD. - Return the final
ans.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Define
MOD = 1_000_000_007and initialize alongcounteransto 0. - Create a frequency map (an array
countsof size 101, since values are 0-100) to store the counts of each number inarr. - Iterate through
arronce to populate thecountsarray. - Iterate through all possible unique value triplets
(x, y, z)that sum to the target. To avoid overcounting, ensurex <= y <= z.- Loop
xfrom0to100. - Loop
yfromxto100. - Calculate
z = target - x - y. - If
zis out of the valid range (z < yorz > 100), continue to the next iteration.
- Loop
- If
counts[x],counts[y], orcounts[z]is zero, this triplet cannot be formed, so continue. - Calculate the number of combinations based on the values of
x,y, andz:- Case 1:
x == y == z: We need to choose 3 items fromcounts[x]. The number of ways isC(counts[x], 3) = counts[x] * (counts[x] - 1) * (counts[x] - 2) / 6. - Case 2:
x == y != z: Choose 2 fromcounts[x]and 1 fromcounts[z]. Ways:C(counts[x], 2) * counts[z]. - Case 3:
x < y == z: Choose 1 fromcounts[x]and 2 fromcounts[y]. Ways:counts[x] * C(counts[y], 2). - Case 4:
x < y < z: Choose 1 from each. Ways:counts[x] * counts[y] * counts[z].
- Case 1:
- Add the calculated combinations to
ans, taking the moduloMODat each step. - Return the final
ans.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.