4Sum

MediumTwo Pointerssort + two pointers

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an integer array nums and an integer target, find every **unique** quadruplet [nums[a], nums[b], nums[c], nums[d]] such that all four indices a, b, c, and d are distinct and the four chosen values sum exactly to target. Return a list of all such quadruplets. The result may be returned in any order, but it must not contain duplicate quadruplets. Two quadruplets are considered the same if they consist of the same multiset of values (the same numbers in the same counts), regardless of the order in which those values were drawn from the array. For example, if both [-1, 0, 0, 1] and [0, -1, 1, 0] could be formed from the array, they count as the **same** quadruplet and should appear only once. The values inside each returned quadruplet may be listed in any order. Aim for an efficient approach rather than checking all four-element combinations explicitly.

Examples

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Three distinct multisets of four values each add up to 0. Any other quadruplet summing to 0 is a reordering of one of these and is therefore a duplicate.
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Although there are several ways to pick four of the five 2s, they all form the same multiset {2,2,2,2}, so only one quadruplet is reported.
Input: nums = [1,2,3,4], target = 100
Output: []
The only possible quadruplet sums to 10, which does not equal the target, so there is no valid answer.

Constraints

  • `0 <= nums.length <= 200`
  • `-10^9 <= nums[i] <= 10^9`
  • `-10^9 <= target <= 10^9`
  • The sum of any four elements is guaranteed to fit in a 64-bit signed integer.
  • Each quadruplet in the output must be unique.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More sort + two pointers problems