3Sum With Multiplicity - Video Solutions

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.