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 <= 300Problem Overview: Given an integer array arr and a target, count the number of triplets (i, j, k) such that i < j < k and arr[i] + arr[j] + arr[k] == target. The twist is multiplicity: duplicate values can produce many valid combinations, so the algorithm must count them correctly without double‑counting.
Approach 1: Two Pointers After Sorting (O(n²) time, O(1) space)
Sort the array first so equal numbers are grouped. Iterate index i as the first element of the triplet. For the remaining portion of the array, use the classic two pointers technique: one pointer left starts at i+1 and another right starts at the end. If the sum is smaller than the target, move left forward; if larger, move right backward. When the sum equals the target, count how many duplicates exist at both ends. If arr[left] == arr[right], all elements between them form valid pairs and you can compute combinations directly. Otherwise count duplicates on both sides and multiply them to get the number of triplets contributed by that value pair.
This method relies on sorting and pointer movement to avoid redundant scans. The array is traversed once per fixed element, giving O(n²) time and constant auxiliary space.
Approach 2: HashMap Frequency Counting (O(n²) time, O(n) space)
Build a frequency map using a hash table that stores how many times each value appears. Iterate through all ordered pairs (a, b) from the array and compute the required third value c = target - a - b. Instead of scanning the array again, check the frequency map to see how many times c occurs.
Careful counting prevents overcounting. Different cases arise depending on whether a, b, and c are equal or distinct. For example, if all three numbers are the same, compute combinations using freq[x] choose 3. If only two values match, use freq[x] choose 2 multiplied by the remaining value's frequency. These combinational counts efficiently handle multiplicity without enumerating every triplet explicitly.
This approach trades additional memory for simpler counting logic and avoids pointer management. Time complexity remains O(n²) because all value pairs are considered, while the hash map introduces O(n) extra space.
Recommended for interviews: The sorted Two Pointers solution is typically preferred. It demonstrates understanding of array manipulation, duplicate handling, and pointer techniques—skills interviewers commonly evaluate in 3Sum‑style problems. Mentioning the hashmap counting strategy shows deeper insight into frequency‑based combinatorics and tradeoffs between time and memory.
This approach involves first sorting the array and then using a two-pointer method to efficiently count the valid tuples. After fixing the first element of the triplet, use two pointers to find complementary pairs that sum up to the required value.
The C solution begins by sorting the input array using Quick Sort. It then iterates over the array and for each element, uses the two-pointer technique to locate pairs that along with the current element add up to the target. Counts of repeated numbers are handled carefully to ensure all combinations are considered.
Time Complexity: O(n^2), where n is the number of elements in the array.
Space Complexity: O(1) apart from the input data since the operation is done in-place.
In this approach, we utilize hashmaps/dictionaries to store the frequency of each number in the array. Then, iterate through unique pairs of numbers to check if the pair with any other number sums up to the target value. This approach makes use of combinatorial calculations without explicitly sorting the array.
This Python solution makes use of combinations evaluated through mathematical formulas counting indirect combinations by their frequency. It differentiates cases where numbers are equal or different and handles all scenarios precisely.
Time Complexity: O(n^2), which comes from iterating over pairs and can be considered effectively O(n) for small arrays using fixed range.
Space Complexity: O(1), as the frequency dictionary can be considered a fixed size due to constraints.
We can use a hash table or an array cnt of length 101 to count the occurrence of each element in the array arr.
Then, we enumerate each element arr[j] in the array arr, first subtract one from cnt[arr[j]], and then enumerate the elements arr[i] before arr[j], calculate c = target - arr[i] - arr[j]. If c is in the range of [0, 100], then the answer is increased by cnt[c], and finally return the answer.
Note that the answer may exceed {10}^9 + 7, so take the modulus after each addition operation.
The time complexity is O(n^2), where n is the length of the array arr. The space complexity is O(C), where C is the maximum value of the elements in the array arr, in this problem C = 100.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Two Pointers Approach | Time Complexity: O(n^2), where n is the number of elements in the array. |
| HashMap Frequency Count | Time Complexity: O(n^2), which comes from iterating over pairs and can be considered effectively O(n) for small arrays using fixed range. |
| Counting + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers After Sorting | O(n^2) | O(1) | Best general approach when the array can be sorted and duplicates must be counted efficiently |
| HashMap Frequency Count | O(n^2) | O(n) | Useful when frequency counting or combinatorics simplifies duplicate handling |
3Sum With Multiplicity | Live Coding with Explanation | Leetcode - 923 • Algorithms Made Easy • 9,689 views views
Watch 9 more video solutions →Practice 3Sum With Multiplicity with our built-in code editor and test cases.
Practice on FleetCode