Skip to main content
Talentd

3Sum With Multiplicity - Solution & Explanation

MediumArrayHash TableTwo PointersSorting17 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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 <= 3000
  • 0 <= arr[i] <= 100
  • 0 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Two Pointers Approach

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.

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.
Space Complexity: O(1), as the frequency dictionary can be considered a fixed size due to constraints.

Counting + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two Pointers After SortingO(n^2)O(1)Best general approach when the array can be sorted and duplicates must be counted efficiently
HashMap Frequency CountO(n^2)O(n)Useful when frequency counting or combinatorics simplifies duplicate handling

Video Solution

3Sum With Multiplicity | Live Coding with Explanation | Leetcode - 923 • Algorithms Made Easy • 9,785 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice 3Sum With Multiplicity with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays