18. 4Sum
Model: qwen3.5:9b
Topics: Array,Hash Table,Two Pointers
FAANG asked: 1
Acceptance rate: 35.1%
Problem Breakdown
We are given an array of integers nums and a target integer value. The goal is to find all unique quadruplets (groups of four numbers) within that array where their sum equals the target.
Key constraints to note:
- Uniqueness: The solution set must not contain duplicate quadruplets. If
[a, b, c, d]sums correctly, we cannot return[-2, -1, 0, 3]if that same combination appears again in a different order or via duplicates from the input array (e.g., multiple zeros). - Input Size: is up to 200. This suggests an algorithm better than brute force () but allows for something like .
- Values: Integers can be negative and large, so we must handle arithmetic carefully (though Python handles arbitrary precision integers automatically).
Intuition
A naive approach would use four nested loops to check every combination of indices where . This results in a time complexity of . Given the constraint , while technically feasible ( billion operations is too high for typical limits), we can optimize significantly.
The core insight comes from reducing this to a Two Sum problem:
If we fix two numbers, say nums[i] and nums[j], the remaining task becomes finding two other numbers that sum up to (target - nums[i] - nums[j]). This is exactly what the Two Pointers technique solves efficiently on a sorted array.
To handle duplicates effectively (which are required for uniqueness), we should sort the input array first. Sorting allows us to easily skip over identical values during iteration, ensuring we don’t generate duplicate quadruplets in our result set.
Approach
- Sort: Sort
numsinitially (). This enables two-pointer logic and easy duplicate skipping. - Outer Loop (First Number): Iterate through the array with index
i.- Skip if we are at a value equal to the previous one (
nums[i] == nums[i-1]) to avoid duplicates for this position.
- Skip if we are at a value equal to the previous one (
- Inner Logic: For each valid
i, initialize two pointers,left(ati + 1) andright(at end of array). - Two Pointers Loop: While
left < right:- Calculate current sum:
nums[i] + nums[left] + nums[right]. Note that we need a second loop or logic to pick the second number? Actually, standard optimization for -Sum is fixing one index and using two pointers on the rest. Wait, 4-Sum requires picking two numbers from the remaining subarray. - Correction: The approach isn’t just “fix i”. We need to fix
i(first number) AND then find pairs in the remainder? No, that’s logic where we iteratejas well. - Refined Approach: Fix index
i. Then use two pointers (left,right) on the subarray[i+1...end]to solve for 2 numbers summing to remainder? No, that solves . If we fixnums[i], we still need three more. - Correct Logic: Fix index
i. Then iterate with a second pointer (or implicitly via two pointers) on the rest of array? - Actually, standard 4Sum is: Iterate
ifrom to . Inside that, use Two Pointers for indicesleft,rightin range[i+1, N-1]. Wait, if we fixnums[i], we need three more numbers. That’s not a standard 2-pointer problem (which finds two numbers). - Wait, the prompt asks for . If I sort and iterate index
ias the first number, then I have to find two other numbers from the remaining array? No, that would be finding pairs. - Let’s re-evaluate: To get 4Sum in , we usually fix two indices ( and ) or iterate
i(first number), then use two pointers to find the remaining three? No, that doesn’t work directly. - Standard Solution Pattern for K-Sum:
- Sort array.
- Loop index
ifrom to . Skip duplicates ofnums[i]. - Inside loop
i, use Two Pointers (left = i+1,right = N-1) on the remaining subarray? No, that only finds one pair summing to remainder if we treat it as .
- Calculate current sum:
Python Solution (Two-Pointers with Early Pruning)
class Solution:
def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 3):
# Avoid duplicate quadruplets for the first element
if i > 0 and nums[i] == nums[i - 1]:
continue
# Early pruning: minimum possible sum is too large
if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
break
# Early pruning: maximum possible sum with nums[i] is too small
if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
continue
for j in range(i + 1, n - 2):
# Avoid duplicate quadruplets for the second element
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# Early pruning for the second loop
if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
break
if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
continue
left, right = j + 1, n - 1
while left < right:
curr_sum = nums[i] + nums[j] + nums[left] + nums[right]
if curr_sum == target:
ans.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
# Skip duplicates for third and fourth elements
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif curr_sum < target:
left += 1
else:
right -= 1
return ans
Key Techniques
- Sorting & Two Pointers: Sorting simplifies finding duplicate elements and allows us to use two outer loops ( and ) along with a two-pointer approach (
leftandright) for the inner sum, reducing time complexity to . - Duplicate Skipping: To prevent duplicate quadruplets in the answer:
- Skip
nums[i]ifnums[i] == nums[i - 1]. - Skip
nums[j]ifnums[j] == nums[j - 1]. - Advance
leftandrightpast identical numbers after finding a valid quadruplet.
- Early Pruning (Optimization): Checking the theoretical minimum and maximum sums for
iandjat each step allows skipping iterations that cannot producetarget, making execution significantly faster.
Complexity
- Time Complexity: — two nested loops over an two-pointer search.
- Space Complexity: additional space (excluding the output list and sorting space).