Four Sum Problem
Description
LeetCode Problem 18. Given an array of integers nums and an integer target, return all unique quadruplets in the array (a, b, c, d), which gives the sum of target (a + b + c + d = target).
Example:
1
2
Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Solution
This problem is similar to the two sum problem.
Brute Force Approach
A simple solution is to use the brute force approach.
We loop through the array four times to get four different elements (a, b, c, d). Then we check whether (a + b + c + d = target) is true or not.
If it is true, we add the quadruplets (a, b, c, d) to a set to ensure the final solutions do not contain duplicates; otherwise, we keep on searching.
The time complexity of this approach is O(n4), and the space complexity is O(n).
Two Pointer Approach
If the array is sorted, we can use the two pointer approach to reduce the time and space complexity
(similar to the three sum problem).
We first sort the array in ascending order, the time complexity of this step is O(nlogn).
In the three sum problem, we iterate through the elements in the array and use the two pointer approach to search the other two elements. In the four sum problem, we can do something similar. We iterate through the array twice to get two elements. Then we use the two pointer approach to search for the other two numbers.
For each two elements nums[i] and nums[j] (nums[i] <= nums[j]) in the array, we set two pointers pointing to the elements larger than nums[j]: the left pointer l points to the smallest element on the right of nums[j], and the right pointer r points to the largest element on the right of nums[j].
We add the four numbers together (nums[i] + nums[j] + nums[l] + nums[r]) and compare it with target.
If the sum is greater than 0, that means nums[r] is too big for the triplet (and nums[l] is already the smallest possible one), so we move the right pointer one step to the left (r-1) to try a smaller number.
If the sum is smaller than 0, that means nums[l] is too small for the triplet (and nums[r] is already the biggest possible one), so we move the left pointer one step to the right (l+1) to try a bigger number.
If the sum is 0, we find one solution and insert it into a set (to make sure the final solutions do not contain duplicates). Then we move the left pointer one step to the right (l+1), and the right pointer one step to the left (r-1). We move the left pointer one step to the right is because if we only move the right pointer and keep the left pointer pointing to the current number, the new nums[r] will be smaller or equal to the old nums[r]. If it is smaller, the sum of these three numbers will be less than 0. If it is equal, then this solution will be the same as the original one. Same reason applies to why we move the right pointer one step to the left.
The time complexity can be reduced to O(n3), while the space complexity is still O(n).
Sample C++ Code
This is a C++ implementation of the two pointer approach.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
set<vector<int>> s;
int l, r, sum;
int len = nums.size();
for (int i = 0; i < len - 3; i ++) {
for (int j = i + 1; j < len - 2; j ++) {
l = j + 1, r = len - 1;
while (l < r) {
sum = nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target) {
s.insert({nums[i], nums[j], nums[l], nums[r]});
l ++;
r --;
} else if (sum > target) {
r --;
} else {
l ++;
}
}
}
}
for (auto x : s) {
ans.push_back(x);
}
return ans;
}
int main() {
vector<int> nums={1,0,-1,0,-2,2};
int target = 0;
vector<vector<int>> ans;
ans = fourSum(nums, target);
for (int i = 0; i < ans.size(); i ++) {
for (int j = 0; j < ans[i].size(); j ++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
}