4Sum

Medium· sort + two pointers· dedup

Problem

Return all unique quadruplets of values from the array, taken at four distinct indices, whose sum equals a given target. No quadruplet may appear twice in the output.

Examples

Input: nums = [1,0,-1,0,-2,2], target = 0

Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [3,3,3,3,3], target = 12

Output: [[3,3,3,3]]

Constraints

• 1 <= nums.length <= 200
• -10^9 <= nums[i], target <= 10^9

Hints & approach

Hint 1

This extends 3Sum by one more fixed element.

Hint 2

Sort, fix two indices with nested loops, then use two pointers for the last pair.

Hint 3

Watch for integer overflow when adding four large values.

Approachtry the hints first

Sort the array. Loop over i, then over j > i, skipping repeated values at each level. For each (i, j), run two pointers on the remaining suffix to find pairs summing to target - nums[i] - nums[j], recording matches and skipping duplicates after each one. Use 64-bit sums to avoid overflow. The two outer loops and the linear inner scan give O(n^3).

Time O(n^3) · Space O(1) extra (ignoring sort and output)

← PreviousContainer With Most Water Next →Trapping Rain Water