4Sum
LeetCode #18 · Medium · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Sorting + Two Pointers (Extension of 3Sum)
Key insight
Sorting the array allows for efficient two-pointer traversal to find pairs that sum to a specific value. 4Sum can be reduced to 3Sum, which reduces to 2Sum by fixing one number at a time.
Strategy
- 1Sort the array.
- 2Iterate through the array with index i (first number).
- 3Iterate with index j > i (second number).
- 4Use two pointers (left, right) for the remaining elements to find
- 5Skip duplicates carefully at every level (i, j, left, right) to ensure
- 6Use long long to prevent integer overflow during sum calculation.
Time
O(N^3)
Space
O(log N) or O(N)
sorting.
Problem description(from LeetCode)
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.
Examples
Example 1
- Input:
- nums = [1,0,-1,0,-2,2], target = 0
- Output:
- [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Constraints
- •1 <= nums.length <= 200
- •-10^9 <= nums[i] <= 10^9
- •-10^9 <= target <= 10^9
C++ Solution
solution.cpp
class Solution {
public:
vector<vector<int>> fourSum(vector<int> &nums, int target) {
vector<vector<int>> result;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = n - 1;
while (left < right) {
lli sum = (lli)nums[i] + nums[j] + nums[left] + nums[right];
if (sum == (lli)target) {
result.push_back({nums[i], nums[j], nums[left], nums[right]});
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < target) left++;
else right--;
}
}
}
return result;
}
};