Master the 4Sum algorithm: Learn how to efficiently find unique quadruplets that sum to a target value using the Two-Pointer technique. Discover optimization strategies, time complexity analysis, and practical implementation tips for this classic coding interview problem.
The 4Sum problem is an extension of the 3Sum problem. The primary challenge is to find all unique quadruplets that sum up to the target value without including duplicates.
Key Insights
Sorting the Array:
Sorting the array upfront simplifies handling duplicates and allows efficient use of pointers.
After sorting, we can use multiple pointers to traverse the array.
Reducing the Problem Complexity:
The brute-force approach would involve four nested loops with a time complexity of O(n^4), which is impractical for large n.
We can reduce the complexity to O(n^3) by fixing two numbers and using the two-pointer technique to find the other two numbers.
Handling Duplicates:
To avoid duplicate quadruplets, we need to skip over duplicate elements during iteration.
Careful consideration is required when incrementing or decrementing pointers to ensure all unique quadruplets are found.
Early Termination (Pruning):
We can add pruning conditions to skip unnecessary iterations when it's impossible to find a valid quadruplet due to the array's sorted nature.
For example, if the smallest possible sum of the current four elements is greater than the target, we can break early.
Approach Overview
Two-Pointer Method with Nested Loops:
Use two nested loops to fix the first two numbers.
Use two pointers (left and right) to find the remaining two numbers.
Move the pointers based on the sum relative to the target.
Skip duplicates at each step to ensure uniqueness.
Dictionary-Based Method:
Less common for the 4Sum problem due to increased complexity in handling duplicates.
For completeness, we'll discuss it briefly but focus on the Two-Pointer method.
Solution 1: Two-Pointer Technique
How It Works
The Two-Pointer technique extends naturally from the 3Sum problem to the 4Sum problem:
Sort the Array: Sorting allows us to use pointers effectively and skip duplicates easily.
Nested Loops for First Two Numbers: Use two nested loops with indices i and j to fix the first two numbers.
Two Pointers for Remaining Two Numbers:
Initialize left to j + 1 and right to len(nums) - 1.
Move left and right to find pairs that sum to target - nums[i] - nums[j].
Adjust Pointers Based on Sum:
If the total sum is less than the target, increment left to increase the sum.
If the total sum is greater than the target, decrement right to decrease the sum.
If the total sum equals the target, record the quadruplet and move both pointers, skipping duplicates.
Skip Duplicates:
After fixing each of the first two numbers, skip over duplicates to prevent duplicate quadruplets.
Similarly, skip duplicates for left and right pointers after finding a valid quadruplet.
Pruning (Optional but Beneficial): Since the array is sorted, we can add conditions to break early from loops if the sum exceeds the target in certain situations.
Code Explanation
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort() # Sort the array
n = len(nums)
result = []
for i in range(n):
# Skip duplicates for the first number
if i > 0 and nums[i] == nums[i - 1]:
continue
# Early termination
if nums[i] * 4 > target and nums[i] >= 0:
break
for j in range(i + 1, n):
# Skip duplicates for the second number
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# Early termination
if nums[i] + nums[j] * 3 > target and nums[j] >= 0:
break
left, right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
result.append([nums[i], nums[j], nums[left], nums[right]])
# Skip duplicates for the third number
while left < right and nums[left] == nums[left + 1]:
left += 1
# Skip duplicates for the fourth number
while left < right and nums[right] == nums[right - 1]:
right -= 1
# Move pointers after recording a valid quadruplet
left += 1
right -= 1
elif total < target:
left += 1 # Need a larger sum
else:
right -= 1 # Need a smaller sum
return result
Step-by-Step Explanation:
Sorting: The array nums is sorted in ascending order.
First Loop (i from 0 to n - 4):
Fixes the first number nums[i].
Skips duplicates by checking if nums[i] == nums[i - 1] when i > 0.
Applies pruning by breaking the loop if nums[i] * 4 > target and nums[i] >= 0, as further sums will only be larger.
Second Loop (j from i + 1 to n - 3):
Fixes the second number nums[j].
Skips duplicates for nums[j].
Applies pruning similarly to the first loop.
Two-Pointer Initialization:
left is set to j + 1.
right is set to n - 1.
While Loop (left < right):
Calculates total = nums[i] + nums[j] + nums[left] + nums[right].
If total == target, a valid quadruplet is found:
Append the quadruplet to result.
Skip duplicates for nums[left] and nums[right].
Move both left and right pointers.
If total < target, increment left to increase the sum.
If total > target, decrement right to decrease the sum.
Return Result:
After all iterations, return the list of unique quadruplets result.
Complexity Analysis
Time Complexity:O(n^3)
The outer two loops run in O(n^2).
The inner while loop can run up to O(n) for each pair of i and j, resulting in O(n^3) overall.
Space Complexity:O(k)
Where k is the number of quadruplets added to the result.
Apart from the output list, we use a constant amount of extra space.
Notes on Pruning and Optimization
Pruning Conditions:
if nums[i] * 4 > target and nums[i] >= 0: break
If the smallest possible sum starting with nums[i] exceeds the target, no further quadruplets can be found.
Similar logic applies to nums[j].
Why Pruning Helps:
Reduces unnecessary iterations.
Particularly effective when dealing with positive numbers and large target values.
Solution 2: Using a Dictionary (Less Efficient for 4Sum)
Overview
While the dictionary-based approach is effective for problems like 2Sum and 3Sum with certain constraints, it's less efficient for 4Sum due to increased complexity in handling duplicates and higher time complexity.
However, for completeness, here's how a dictionary-based approach might work:
Count Frequencies: Create a frequency map of numbers in nums.
Iterate Over Triplets: Use nested loops to fix the first three numbers.
Check for the Fourth Number:
Calculate the required fourth number as val = target - (nums[i] + nums[j] + nums[k]).
Check if val exists in the frequency map.
Ensure that the count of val in the frequency map accounts for its usage in the triplet.
Store Unique Quadruplets: Use a set to store unique quadruplets (converted to tuples for hashability).
Code Explanation
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
from collections import Counter
freq = Counter(nums)
n = len(nums)
ans = set()
nums.sort()
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
val = target - (nums[i] + nums[j] + nums[k])
# Ensure val is not used more times than it appears
count = Counter([nums[i], nums[j], nums[k]])
if freq[val] > count[val]:
quadruplet = tuple(sorted([nums[i], nums[j], nums[k], val]))
ans.add(quadruplet)
return [list(q) for q in ans]
Step-by-Step Explanation:
Frequency Map: Use Counter from the collections module to count the frequency of each number.
Triple Nested Loops:
Fix the first three numbers using indices i, j, and k.
This results in O(n^3) time complexity.
Calculate the Fourth Number: val = target - (nums[i] + nums[j] + nums[k]).
Check Validity:
Use the frequency map to ensure that val exists in nums and hasn't been used more times than it appears.
Create a Counter for the current triplet to check the usage of val.
Store Unique Quadruplets: Convert the quadruplet to a tuple and add it to a set to ensure uniqueness.
Return Result:
Convert the set of tuples back to a list of lists before returning.
Complexity Analysis
Time Complexity:O(n^3)
Triple nested loops result in O(n^3) time.
Note that dictionary operations add some overhead.
Space Complexity:O(n^3)
The set ans can grow up to O(n^3) in the worst case.
The frequency map and counters use additional space.
Why This Approach is Less Efficient
Higher Overhead:
Using Counter and checking frequencies adds computational overhead.
Difficulty Handling Duplicates:
Managing counts and ensuring duplicates are handled correctly complicates the implementation.
Inefficient for Larger n:
Triple nested loops are acceptable for small n but become impractical as n grows.
Key Takeaways
Two-Pointer Technique Extends to 4Sum: By fixing two numbers and using two pointers for the remaining two, we can efficiently find all unique quadruplets.
Sorting is Essential: Sorting the array simplifies handling duplicates and allows for effective pruning.
Pruning Enhances Performance: Early termination conditions can significantly reduce the number of iterations, especially in sorted arrays with positive numbers.
Avoiding Duplicates Requires Care: Skipping duplicate elements at each level of iteration ensures the uniqueness of quadruplets.
Dictionary-Based Approach is Less Practical for 4Sum: While possible, it introduces complexity and is less efficient compared to the Two-Pointer method for this problem.
Time Complexity Considerations: The optimal solution operates in O(n^3) time, which is acceptable for moderate n but can be slow for very large arrays.
Conclusion
The 4Sum problem builds upon the strategies used in the 3Sum problem, extending the use of the Two-Pointer technique within nested loops. By carefully handling duplicates and employing pruning strategies, we can efficiently find all unique quadruplets that sum to the target value.
Understanding and implementing these techniques not only solves the 4Sum problem but also provides a foundation for tackling similar problems that involve finding combinations of numbers that meet specific criteria.
Discussion
Fuel my Writing ⛽
Every creator needs fuel to keep going. If my work has helped you, a small tip would make my day and help me create more!
Discussion