3Sum With Multiplicity

3Sum With Multiplicity

What is this problem about?

The 3Sum With Multiplicity interview question is a variation where the input array may contain many duplicate numbers. You need to find the number of triplets $(i, j, k)$ such that $i < j < k$ and $nums[i] + nums[j] + nums[k] = target$. Because the answer can be very large, you are usually asked to return the result modulo $10^9 + 7$.

Why is this asked in interviews?

Companies like Meta and Amazon use this to evaluate a candidate’s proficiency with Hash Tables and combinatorics. It moves beyond simple pointer manipulation into the realm of frequency counting and mathematical combinations (nCr).

Algorithmic pattern used

The primary pattern is Counting (Hash Table) or Sorting with Two Pointers.

1. Counting: Store the frequency of each number. Iterate through unique pairs $(x, y)$ and calculate the required $z = target - x - y$. Use combinations to find how many ways you can pick $x, y,$ and $z$ based on their frequencies.
2. Two Pointers: Sort the array and use pointers, but when a match is found, count the occurrences of the left and right values to handle the "multiplicity" in bulk.

Example explanation

Input: nums = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5], target = 8.

• If you pick unique values 1, 2, 5, their sum is 8.
• However, there are two 1s, two 2s, and two 5s.
• The number of ways to pick one of each is $2 \times 2 \times 2 = 8$ ways.
• You must do this for all sets of values $(x, y, z)$ that sum to 8.

Common mistakes candidates make

• Ignoring the Modulo: Forgetting to apply modulo $10^9 + 7$ at each addition step, leading to integer overflow.
• Combinatorics Errors: Incorrectly calculating ways to pick elements (e.g., if $x=y$, the number of ways is $count(x) \times (count(x)-1) / 2$).
• Complexity: Trying to use a standard 3Sum approach without accounting for frequencies, which becomes very slow if the array is large but has few unique numbers.

Interview preparation tip

When an array has many duplicates, think about frequency maps. Processing "unique values + their counts" is often much faster than processing the raw array.