4Sum

4Sum

What is this problem about?

The 4Sum interview question is a natural evolution of the popular 2Sum and 3Sum problems. Given an array of integers and a specific target value, you need to find all unique quadruplets $[nums[a], nums[b], nums[c], nums[d]]$ such that their sum equals the target. The core challenge is navigating the increased complexity while ensuring that no duplicate quadruplets are included in your final result.

Why is this asked in interviews?

Top companies like Uber, Microsoft, and Meta use the 4Sum coding problem to test a candidate's ability to generalize algorithms. While 3Sum is common, 4Sum forces you to think about nested loops and pointer management more deeply. It evaluates how you handle $O(N^3)$ time complexity efficiently and whether you can manage duplicate sets in a sorted environment without using excessive memory.

Algorithmic pattern used

This problem follows the Two Pointers interview pattern nested within multiple loops. After Sorting the array, you fix the first two numbers using two nested loops and then use the Two Pointers technique (left and right) to find the remaining two numbers. Sorting is the "secret sauce" here because it allows you to skip duplicate values easily and move pointers based on whether your current sum is too high or too low.

Example explanation

Imagine an array [2, 2, 2, 2, 2] with a target of 8.

1. Sort the array (it's already sorted).
2. Fix the first index $i=0$ and second index $j=1$.
3. Set Left to $j+1$ and Right to the end of the array.
4. The sum is $2+2+2+2 = 8$. We found a quadruplet.
5. To avoid duplicates, the algorithm must skip the remaining 2s for all four positions to ensure only one unique [2, 2, 2, 2] is returned.

Common mistakes candidates make

• Missing Duplicate Checks: Forgetting to skip identical adjacent elements inside the loops, resulting in the same quadruplet being added multiple times.
• Integer Overflow: In some languages, adding four large integers can exceed the standard 32-bit integer limit. Using 64-bit integers for the sum is a safer bet.
• Suboptimal Complexity: Trying to use a Hash Map for the 4th element inside three loops can work, but it often increases space complexity without improving the $O(N^3)$ time bound.

Interview preparation tip

When you see a problem asking for $K$ elements summing to a target, remember that the general approach is $K-2$ nested loops combined with one final Two Pointer pass. This reduces the brute-force $O(N^K)$ to $O(N^{K-1})$.