3Sum With Multiplicity solution and explanation
Google
9 more videos on this problem
3Sum With Multiplicity | Live Coding with Explanation | Leetcode - 923Algorithms Made Easy · 10:56 · 9K views
3Sum With Multiplicity | Leetcode 923 | Two pointers | Day-6Ayushi Sharma · 15:41 · 8K views
3Sum With Multiplicity | Leetcode 923 | Maps | Live Coding SessionCoding Decoded · 25:14 · 4K views
Leetcode - 3Sum With Multiplicity (Python)Timothy H Chang · 8:50 · 3K views
3Sum With Multiplicity | Leetcode 923 |Maps 🔥🔥 | Live coding sessionCoding Decoded · 1:38 · 2K views
LeetCode 923. 3Sum With MultiplicityHappy Coding · 21:13 · 2K views
923. 3Sum With MultiplicityTech Adora by Nivedita · 13:23 · 1K views
3Sum With Multiplicity | Two Pointers | HashTable | Sortings | 923 LeetCode | Day 06CodeWithSunny · 17:27 · 1K views
Daily Leetcode #736: Apr 06, 2022 - 923. 3Sum With MultiplicityProgramming Live with Larry · 18:47 · 1K views
3Sum With Multiplicity | LeetCode 923 | Coders CampCoders Camp · 9:47 · 940 views
The problem
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
Approach overview
Problem 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.
Approach 1: Two Pointers Approach
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.
class Solution:
def threeSumMulti(self, arr, target):
from collections import Counter
MOD = 10**9 + 7
arr.sort()
count = Counter(arr)
result = 0
for i, x in enumerate(arr):
T = target - x
j, k = i + 1, len(arr) - 1
while j < k:
if arr[j] + arr[k] < T:
j += 1
elif arr[j] + arr[k] > T:
k -= 1
else:
if arr[j] != arr[k]:
result += count[arr[j]] * count[arr[k]]
result %= MOD
j += 1
k -= 1
else:
result += (count[arr[j]] * (count[arr[j]] - 1)) // 2
result %= MOD
break
return result
# Example usage
solution = Solution()
arr = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
target = 8
print(solution.threeSumMulti(arr, target)) # Output: 20import java.util.Arrays;
class ThreeSumMultiplicity {
public int threeSumMulti(int[] arr, int target) {
Arrays.sort(arr);
long result = 0;
int MOD = 1_000_000_007;
for (int i = 0; i < arr.length; ++i) {
int T = target - arr[i];
int j = i + 1, k = arr.length - 1;
while (j < k) {
if (arr[j] + arr[k] < T) {
j++;
} else if (arr[j] + arr[k] > T) {
k--;
} else {
if (arr[j] != arr[k]) {
int left = 1, right = 1;
while (j + 1 < k && arr[j] == arr[j + 1]) {
left++;
j++;
}
while (k - 1 > j && arr[k] == arr[k - 1]) {
right++;
k--;
}
result += left * right;
result %= MOD;
j++;
k--;
} else {
result += (k - j + 1) * (k - j) / 2;
result %= MOD;
break;
}
}
}
}
return (int) result;
}
public static void main(String[] args) {
ThreeSumMultiplicity solution = new ThreeSumMultiplicity();
int[] arr = {1,1,2,2,3,3,4,4,5,5};
int target = 8;
System.out.println(solution.threeSumMulti(arr, target)); // Output: 20
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int threeSumMulti(vector<int>& arr, int target) {
sort(arr.begin(), arr.end());
const int MOD = 1e9 + 7;
long result = 0;
int n = arr.size();
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 {
if (arr[j] != arr[k]) {
int left = 1, right = 1;
while (j + 1 < k && arr[j] == arr[j + 1]) {
++left;
++j;
}
while (k - 1 > j && arr[k] == arr[k - 1]) {
++right;
--k;
}
result += left * right;
result %= MOD;
++j;
--k;
} else {
result += (k - j + 1) * (k - j) / 2;
result %= MOD;
break;
}
}
}
}
return result;
}
};
int main() {
Solution solution;
vector<int> arr = {1,1,2,2,3,3,4,4,5,5};
int target = 8;
int result = solution.threeSumMulti(arr, target);
cout << result << endl; // Output: 20
return 0;
}var threeSumMulti = function(arr, target) {
arr.sort((a, b) => a - b);
const MOD = 1e9 + 7;
let result = 0;
for (let i = 0; i < arr.length; i++) {
let j = i + 1, k = arr.length - 1;
const T = target - arr[i];
while (j < k) {
if (arr[j] + arr[k] < T) {
j++;
} else if (arr[j] + arr[k] > T) {
k--;
} else if (arr[j] !== arr[k]) {
let left = 1, right = 1;
while (j + 1 < k && arr[j] === arr[j + 1]) { left++; j++; }
while (k - 1 > j && arr[k] === arr[k - 1]) { right++; k--; }
result += left * right;
result %= MOD;
j++;
k--;
} else {
result += (k - j + 1) * (k - j) / 2;
result %= MOD;
break;
}
}
}
return result;
};
// Example usage
console.log(threeSumMulti([1,1,2,2,3,3,4,4,5,5], 8)); // Output: 20#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int threeSumMulti(int* arr, int arrSize, int target) {
qsort(arr, arrSize, sizeof(int), compare);
long long result = 0;
for (int i = 0; i < arrSize; i++) {
int j = i + 1, k = arrSize - 1;
int remainder = target - arr[i];
while (j < k) {
if (arr[j] + arr[k] < remainder) {
j++;
} else if (arr[j] + arr[k] > remainder) {
k--;
} else if (arr[j] != arr[k]) {
int leftCount = 1, rightCount = 1;
while (j + 1 < k && arr[j] == arr[j + 1]) {
leftCount++;
j++;
}
while (k - 1 > j && arr[k] == arr[k - 1]) {
rightCount++;
k--;
}
result += (leftCount * rightCount) % MOD;
result %= MOD;
j++;
k--;
} else {
// arr[j] == arr[k]
result += ((k - j + 1) * (k - j) / 2) % MOD;
result %= MOD;
break;
}
}
}
return (int) result;
}
int main() {
int arr[] = {1,1,2,2,3,3,4,4,5,5};
int target = 8;
int result = threeSumMulti(arr, 10, target);
printf("%d\n", result); // Output: 20
return 0;
}using System;
using System.Collections.Generic;
public class ThreeSumMultiplicity {
public int ThreeSumMulti(int[] arr, int target) {
Array.Sort(arr);
long result = 0;
int MOD = 1000000007;
for (int i = 0; i < arr.Length; i++) {
int T = target - arr[i];
int j = i + 1, k = arr.Length - 1;
while (j < k) {
if (arr[j] + arr[k] < T) {
j++;
} else if (arr[j] + arr[k] > T) {
k--;
} else {
if (arr[j] != arr[k]) {
int left = 1, right = 1;
while (j + 1 < k && arr[j] == arr[j + 1]) {
left++;
j++;
}
while (k - 1 > j && arr[k] == arr[k - 1]) {
right++;
k--;
}
result += left * right;
result %= MOD;
j++;
k--;
} else {
result += (k - j + 1) * (k - j) / 2;
result %= MOD;
break;
}
}
}
}
return (int)result;
}
public static void Main() {
int[] arr = {1,1,2,2,3,3,4,4,5,5};
int target = 8;
ThreeSumMultiplicity solution = new ThreeSumMultiplicity();
Console.WriteLine(solution.ThreeSumMulti(arr, target)); // Output: 20
}
}This Python solution makes use of the Counter class for frequency counting after sorting the array. It iterates over the array while applying two pointers to find all valid triplets by checking the pairs and adjusting counts for elements. The result is taken modulo the given large number.
Time Complexity: O(n^2), where n is the number of elements in the array.
Space Complexity: O(1), excluding the input array space.
Approach 2: HashMap Frequency Count
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.
class Solution:
def threeSumMulti(self, arr, target):
MOD = 10**9 + 7
count = Counter(arr)
result = 0
for i in count:
for j in count:
k = target - i - j
if k in count:
if i == j == k:
result += count[i] * (count[i] - 1) * (count[i] - 2) // 6
elif i == j != k:
result += count[i] * (count[i] - 1) // 2 * count[k]
elif i < j < k:
result += count[i] * count[j] * count[k]
return result % MOD
# Example usage
solution = Solution()
arr = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
target = 8
print(solution.threeSumMulti(arr, target)) # Output: 20import java.util.HashMap;
import java.util.Map;
class ThreeSumMultiplicity {
public int threeSumMulti(int[] arr, int target) {
int MOD = 1_000_000_007;
Map<Integer, Long> count = new HashMap<>();
for (int x : arr) {
count.put(x, count.getOrDefault(x, 0L) + 1);
}
long result = 0;
for (int i : count.keySet()) {
for (int j : count.keySet()) {
int k = target - i - j;
if (!count.containsKey(k)) continue;
if (i == j && j == k) {
result += count.get(i) * (count.get(i) - 1) * (count.get(i) - 2) / 6;
} else if (i == j && j != k) {
result += count.get(i) * (count.get(i) - 1) / 2 * count.get(k);
} else if (i < j && j < k) {
result += count.get(i) * count.get(j) * count.get(k);
}
result %= MOD;
}
}
return (int) result;
}
public static void main(String[] args) {
ThreeSumMultiplicity solution = new ThreeSumMultiplicity();
int[] arr = {1,1,2,2,3,3,4,4,5,5};
int target = 8;
System.out.println(solution.threeSumMulti(arr, target)); // Output: 20
}
}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.
Approach 3: Counting + Enumeration
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.
function threeSumMulti(arr: number[], target: number): number {
const mod = 10 ** 9 + 7;
const cnt: number[] = Array(101).fill(0);
for (const x of arr) {
++cnt[x];
}
let ans = 0;
const n = arr.length;
for (let j = 0; j < n; ++j) {
--cnt[arr[j]];
for (let i = 0; i < j; ++i) {
const c = target - arr[i] - arr[j];
if (c >= 0 && c < cnt.length) {
ans = (ans + cnt[c]) % mod;
}
}
}
return ans;
}func threeSumMulti(arr []int, target int) (ans int) {
const mod int = 1e9 + 7
cnt := [101]int{}
for _, x := range arr {
cnt[x]++
}
for j, b := range arr {
cnt[b]--
for _, a := range arr[:j] {
if c := target - a - b; c >= 0 && c < len(cnt) {
ans = (ans + cnt[c]) % mod
}
}
}
return
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is 3Sum With Multiplicity easy or hard?
The problem is generally classified as Medium difficulty. The core logic resembles the classic 3Sum pattern, but correctly counting duplicates and computing multiplicities adds an extra layer of reasoning compared with simpler triplet problems.
3Sum With Multiplicity Python/Java solution
Python and Java implementations commonly sort the array and apply a two‑pointer scan for each fixed index. The logic counts duplicates on both sides when a valid sum is found. Another implementation uses a HashMap or dictionary to store frequencies and compute combinations for repeated values.
How to solve 3Sum With Multiplicity in O(n)?
A strict O(n) solution is generally not achievable because the algorithm must consider pairs of numbers to determine the third value. The best practical complexity is O(n^2), either with sorting plus two pointers or by iterating pairs with a hashmap frequency count.
What is the best approach for 3Sum With Multiplicity?
The most common interview solution sorts the array and applies the two pointers technique. Fix one number, then move two pointers across the remaining subarray to find pairs that complete the target sum. Duplicate values are counted using combinational logic, giving O(n^2) time and O(1) extra space.
Is 3Sum With Multiplicity asked at Google/Amazon/Meta?
3Sum‑style problems are common in interviews at companies like Amazon, Google, and Meta because they test array manipulation, duplicate handling, and two‑pointer reasoning. Variants such as 3Sum, 3Sum Closest, and 3Sum With Multiplicity appear frequently in technical interview practice sets.
What data structure is used in 3Sum With Multiplicity?
Typical implementations rely on arrays combined with either the two pointers technique after sorting or a hashmap for frequency counting. The hashmap approach tracks how many times each value appears, enabling efficient combinational counting of valid triplets.
What is the time complexity of 3Sum With Multiplicity?
Most efficient solutions run in O(n^2) time. The array is sorted once in O(n log n), then each element is used as a starting point while a two‑pointer scan processes the remaining elements. Space complexity can be O(1) with the two‑pointer method or O(n) when using a hashmap frequency table.