DSA interview question

4Sum

Medium · Algorithms · Topics: array, two pointer, sorting

The problem

A budgeting tool helps a family pick four different expenses that add up exactly to a monthly target, listing each distinct combination of amounts once. It's 3Sum with one more loop: sort, fix two values, and two-pointer the rest, skipping duplicates at all four levels. The one new trap is overflow: four values near 10^9 add up to about 4 × 10^9, which wraps around in a 32-bit int and can produce false matches. The sums must be computed in 64 bits.

Example: [1, 0, -1, 0, -2, 2], target 0 → [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]].

Function signature

vector<vector<int>> fourSum(vector<int> nums, long long target);  // unique quadruplets summing to target

Test cases

Input `(nums, target)`	Output	Explanation
`([1, 0, -1, 0, -2, 2], 0)`	`[[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]`
`([2, 2, 2, 2, 2], 8)`	`[[2,2,2,2]]`	Reported once
`([0, 0, 0, 0], 0)`	`[[0,0,0,0]]`
`([1000000000 ×4], -294967296)`	`[]`	The true sum is 4 × 10^9; a 32-bit sum would wrap to -294967296 and falsely match
`([1, 2, 3], 6)`	`[]`	Fewer than four elements

(Confirm: four different indices; distinct value combinations only; sums computed in 64 bits.)

How interviewers phrase it

"Find all unique quadruplets that sum to a target" (LeetCode 18).
The general "k-sum" follow-up: reduce k-sum to (k − 1)-sum recursively down to a two-pointer 2-sum.

Clarifying questions to ask

Unique quadruplets by value?
Can values be large enough to overflow 32-bit sums?
How large is n? (O(n³) is the standard bound.)

Follow-ups to expect

"How does this relate to 3Sum?"
"Where can overflow happen?"
"How do you skip duplicates at the second level?"
"How would you write general k-sum?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview