4Sum
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
