Problem Statement: Given an array of N integers, your task is to find unique quads that add up to give a target value. In short, you need to return an array of all the unique quadruplets [arr[a], arr[b], arr[c], arr[d]] such that their sum is equal to a given target.
Pre-req: 3-sum problem and 2-sum problem
Note:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
arr[a] + arr[b] + arr[c] + arr[d] == target
Examples
Example 1: Input Format: arr[] = [1,0,-1,0,-2,2], target = 0 Result: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] Explanation: We have to find unique quadruplets from the array such that the sum of those elements is equal to the target sum given that is 0. The result obtained is such that the sum of the quadruplets yields 0. Example 2: Input Format: arr[] = [4,3,3,4,4,2,1,2,1,1], target = 9 Result: [[1,1,3,4],[1,2,2,4],[1,2,3,3]] Explanation: The sum of all the quadruplets is equal to the target i.e. 9.
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Brute Force Approach
Algorithm / Intuition
Solution:
In the question, it is clearly stated that for each case the picked indices i.e. a, b, c, and d must be distinct. This means [arr[1], arr[1], arr[2], arr[3]] is not valid and also remember [arr[1], arr[0], arr[2], arr[3]] and [arr[0], arr[1], arr[2], arr[3]] will be considered same.
Naive Approach (Brute-force):
Approach:
The steps are as follows:
- First, we will declare a set data structure as we want unique quadruplets.
- Then we will use the first loop(say i) that will run from 0 to n-1.
- Inside it, there will be the second loop(say j) that will run from i+1 to n-1.
- Then there will be the third loop(say k) that runs from j+1 to n-1.
- Inside loop k, the fourth loop(say l) will run from k+1 to n-1.
- Now, inside these four nested loops, we will check the sum i.e. arr[i]+arr[j]+arr[k]+arr[l], and if it is equal to the target we will sort this quadruplet and insert it in the set data structure.
- Finally, we will return a list of stored quadruplets.
Intuition: This approach is pretty straightforward. Here, we will check all possible quadruplets using 4 loops(as we did in the 3-sum problem) and among them, we will consider the ones whose sum is equal to the given target. And before considering them as our answer we need to sort the quadruplets in ascending order.
Note: For a better understanding of intuition, please watch the video at the bottom of the page.
Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size(); //size of the array
set<vector<int>> st;
//checking all possible quadruplets:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
for (int l = k + 1; l < n; l++) {
// taking bigger data type
// to avoid integer overflow:
long long sum = nums[i] + nums[j];
sum += nums[k];
sum += nums[l];
if (sum == target) {
vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};
sort(temp.begin(), temp.end());
st.insert(temp);
}
}
}
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}
int main()
{
vector<int> nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
int target = 9;
vector<vector<int>> ans = fourSum(nums, target);
cout << "The quadruplets are: \n";
for (auto it : ans) {
cout << "[";
for (auto ele : it) {
cout << ele << " ";
}
cout << "] ";
}
cout << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length; // size of the array
Set<List<Integer>> set = new HashSet<>();
// checking all possible quadruplets:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
for (int l = k + 1; l < n; l++) {
// taking bigger data type
// to avoid integer overflow:
long sum = (long)nums[i] + nums[j];
sum += nums[k];
sum += nums[l];
if (sum == target) {
List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k], nums[l]);
Collections.sort(temp);
set.add(temp);
}
}
}
}
}
List<List<Integer>> ans = new ArrayList<>(set);
return ans;
}
public static void main(String[] args) {
int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
int target = 9;
List<List<Integer>> ans = fourSum(nums, target);
System.out.println("The quadruplets are: ");
for (List<Integer> it : ans) {
System.out.print("[");
for (int ele : it) {
System.out.print(ele + " ");
}
System.out.print("] ");
}
System.out.println();
}
}
from typing import List
from collections import deque
def fourSum(nums: List[int], target: int) -> List[List[int]]:
n = len(nums) # size of the array
st = set()
# checking all possible quadruplets:
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
for l in range(k + 1, n):
# taking bigger data type
# to avoid integer overflow:
sum = nums[i] + nums[j]
sum += nums[k]
sum += nums[l]
if sum == target:
temp = [nums[i], nums[j], nums[k], nums[l]]
temp.sort()
st.add(tuple(temp))
ans = [list(x) for x in st]
return ans
if __name__ == '__main__':
nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1]
target = 9
ans = fourSum(nums, target)
print("The quadruplets are:")
for it in ans:
print("[", end="")
for ele in it:
print(ele, end=" ")
print("]", end=" ")
print()
function fourSum(nums, target) {
let n = nums.length;
let set = new Set();
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
for (let l = k + 1; l < n; l++) {
let sum = nums[i] + nums[j] + nums[k] + nums[l];
if (sum === target) {
let temp = [nums[i], nums[j], nums[k], nums[l]];
temp.sort((a, b) => a - b);
set.add(temp);
}
}
}
}
}
let ans = Array.from(set);
return ans;
}
let nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1];
let target = 9;
let ans = fourSum(nums, target);
console.log("The quadruplets are: ");
for (let it of ans) {
process.stdout.write("[");
for (let ele of it) {
process.stdout.write(ele + " ");
}
process.stdout.write("] ");
}
console.log();
Output: The quadruplets are: [1 1 3 4 ] [1 2 2 4 ] [1 2 3 3 ]
Complexity Analysis
Time Complexity: O(N4), where N = size of the array.
Reason: Here, we are mainly using 4 nested loops. But we not considering the time complexity of sorting as we are just sorting 4 elements every time.
Space Complexity: O(2 * no. of the quadruplets) as we are using a set data structure and a list to store the quads.
Better Approach
Algorithm / Intuition
Better Approach (Using 3 loops and set data structure):
Approach:
The steps are as follows:
- First, we will declare a set data structure as we want unique quadruplets.
- Then we will use the first loop(say i) that will run from 0 to n-1.
- Inside it, there will be the second loop(say j) that will run from i+1 to n-1.
- Before the third loop, we will declare a HashSet to store the specific array elements as we intend to search the fourth element in that HashSet.
- Then there will be the third loop(say k) that runs from j+1 to n-1.
- Inside the third loop, we will calculate the value of the fourth element i.e. target – (nums[i]+nums[j]+nums[k]).
- If the fourth element exists in the HashSet, we will sort these four values i.e. nums[i], nums[j], nums[k], and the fourth element, and insert it in the set data structure declared in step 1.
- After that, we will insert the k-th element i.e. nums[k] in the HashSet as we only want to insert those array elements that are in between indices j and k.
- Finally, we will return a list of stored quadruplets stored in the set data structure.
Intuition:
In the previous approach, we were using 4 loops but in this, we want to reduce that to 3 loops. We have to somehow manage to calculate nums[l] as we are planning to remove the fourth loop(i.e. l). In order to calculate nums[l], we can derive a formula like the following:
nums[l] = target - (nums[i]+nums[j]+nums[k])
So, we will first calculate the triplets nums[i], nums[j], and nums[k] using 3 loops and for the fourth one i.e. nums[l] we will not use another loop and instead we will look up the value target-(nums[i]+nums[j]+nums[k]) in the array. Thus we can remove the fourth loop from the algorithm.
For implementing the search operation of the fourth element, we will use a similar technique as we used in the case of the 3-sum problem. We will store all the elements between the indices j and k in a HashSet and then we will search for the fourth element in the HashSet.
Why we are not inserting all the array elements in the HashSet and then searching for the fourth element:
Let’s understand this intuition using an example. Assume the given array is {1, 2, -1, -2, 2, 0, -1} and the target = 0. Now, we will notice a situation like the following:
Now, the fourth element should be target-(nums[i]+nums[j]+nums[k]) = 0 – (1-1+0) = 0. Now, if all the array elements are in the HashSet and we search for 0, we will end up taking the 0 at index k again. The quadruplets will be {nums[i], nums[j], nums[k], nums[k]} but this is absolutely incorrect. That is why we need to only consider the elements that are in between the indices j and k.
Note: For a better understanding of intuition, please watch the video at the bottom of the page.
Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size(); //size of the array
set<vector<int>> st;
//checking all possible quadruplets:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
set<long long> hashset;
for (int k = j + 1; k < n; k++) {
// taking bigger data type
// to avoid integer overflow:
long long sum = nums[i] + nums[j];
sum += nums[k];
long long fourth = target - sum;
if (hashset.find(fourth) != hashset.end()) {
vector<int> temp = {nums[i], nums[j], nums[k], (int)(fourth)};
sort(temp.begin(), temp.end());
st.insert(temp);
}
// put the kth element into the hashset:
hashset.insert(nums[k]);
}
}
}
vector<vector<int>> ans(st.begin(), st.end());
return ans;
}
int main()
{
vector<int> nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
int target = 9;
vector<vector<int>> ans = fourSum(nums, target);
cout << "The quadruplets are: \n";
for (auto it : ans) {
cout << "[";
for (auto ele : it) {
cout << ele << " ";
}
cout << "] ";
}
cout << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length; // size of the array
Set<List<Integer>> st = new HashSet<>();
// checking all possible quadruplets:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
Set<Long> hashset = new HashSet<>();
for (int k = j + 1; k < n; k++) {
// taking bigger data type
// to avoid integer overflow:
long sum = nums[i] + nums[j];
sum += nums[k];
long fourth = target - sum;
if (hashset.contains(fourth)) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
temp.add((int) fourth);
temp.sort(Integer::compareTo);
st.add(temp);
}
// put the kth element into the hashset:
hashset.add((long) nums[k]);
}
}
}
List<List<Integer>> ans = new ArrayList<>(st);
return ans;
}
public static void main(String[] args) {
int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
int target = 9;
List<List<Integer>> ans = fourSum(nums, target);
System.out.println("The quadruplets are: ");
for (List<Integer> it : ans) {
System.out.print("[");
for (Integer ele : it) {
System.out.print(ele + " ");
}
System.out.print("] ");
}
System.out.println();
}
}
from typing import List
import itertools
def fourSum(nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
st = set()
# checking all possible quadruplets:
for i in range(n):
for j in range(i+1, n):
hashset = set()
for k in range(j+1, n):
# taking bigger data type to avoid integer overflow:
sum_ = nums[i] + nums[j] + nums[k]
fourth = target - sum_
if fourth in hashset:
temp = [nums[i], nums[j], nums[k], fourth]
temp.sort()
st.add(tuple(temp))
# put the kth element into the hashset:
hashset.add(nums[k])
ans = [list(t) for t in st]
return ans
if __name__ == '__main__':
nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1]
target = 9
ans = fourSum(nums, target)
print("The quadruplets are:")
for it in ans:
print("[", end="")
for ele in it:
print(ele, end=" ")
print("]", end=" ")
print()
function fourSum(nums, target) {
let n = nums.length;
let set = new Set();
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
let hashset = new Set();
for (let k = j + 1; k < n; k++) {
let sum = nums[i] + nums[j];
sum += nums[k];
let fourth = target - sum;
if (hashset.has(fourth)) {
let temp = [nums[i], nums[j], nums[k], fourth];
temp.sort((a, b) => a - b);
set.add(temp);
}
hashset.add(nums[k]);
}
}
}
let ans = Array.from(set);
return ans;
}
let nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1];
let target = 9;
let ans = fourSum(nums, target);
console.log("The quadruplets are: ");
for (let it of ans) {
process.stdout.write("[");
for (let ele of it) {
process.stdout.write(ele + " ");
}
process.stdout.write("] ");
}
console.log();
Output: The quadruplets are: [1 1 3 4 ] [1 2 2 4 ] [1 2 3 3 ]
Complexity Analysis
Time Complexity: O(N3*log(M)), where N = size of the array, M = no. of elements in the set.
Reason: Here, we are mainly using 3 nested loops, and inside the loops there are some operations on the set data structure which take log(M) time complexity.
Space Complexity: O(2 * no. of the quadruplets)+O(N)
Reason: we are using a set data structure and a list to store the quads. This results in the first term. And the second space is taken by the set data structure we are using to store the array elements. At most, the set can contain approximately all the array elements and so the space complexity is O(N).
Optimal Approach
Algorithm / Intuition
Optimal Approach:
In this approach, we intend to get rid of two things i.e. the HashSet we were using for the look-up operation and the set data structure used to store the unique quadruplets.
Again the solution to this will be similar to the optimal approach of the 3-sum problem. In that approach, we had fixed a pointer i, and the rest 2 pointers were moving. Similarly, here, as we are dealing with quads instead of triplets we will fix 2 pointers i.e. i and j and the rest of the 2 pointers will be moving.
Now, we need to first understand what the HashSet and the set were doing to make our algorithm work without them. So, the set data structure was basically storing the unique quadruplets in sorted order and the HashSet was used to search for the fourth element.
To get the quadruplets in sorted order, we will sort the entire array in the first step and to get the unique quads, we will simply skip the duplicate numbers while moving the pointers.
How to skip duplicate numbers:
As the entire array is sorted, the duplicate numbers will be in consecutive places. So, while moving a pointer, we will check the current element and the adjacent element. Until they become different, we will move the pointer by 1 place. We will follow this process for all 4 pointers. Thus, we can easily skip the duplicate elements while moving the pointers.
Now, we can also remove the HashSet as we have two moving pointers i.e. k and l that will find the appropriate value of nums[k] and nums[l]. So, we do not need the HashSet anymore.
The process will look like the following:
Among the 4 pointers, 2 will be fixed and 2 will be moving. In each iteration, we will check if the sum i.e. nums[i]+nums[j]+nums[k]+nums[l] is equal to the target.
- If the sum is greater, then we need lesser elements and so we will decrease the value of l.
- If the sum is lesser than the target, we need a bigger value and so we will increase the value of k.
- If the sum is equal to the target, we will simply insert the quad i.e. nums[i], nums[j], nums[k], and nums[l] into our answer and move the pointers k and l skipping the duplicate elements.
Approach:
The steps are as follows:
- First, we will sort the entire array.
- We will use a loop(say i) that will run from 0 to n-1. This i will represent one of the fixed pointers. In each iteration, this value will be fixed for all different values of the rest of the 3 pointers. Inside the loop, we will first check if the current and the previous element is the same and if it is we will do nothing and continue to the next value of i.
- After checking inside the loop, we will introduce another fixed pointer j(runs from i+1 to n-1) using another loop. Inside this second loop, we will again check for duplicate elements and only perform any further operation if the elements are different.
- Inside the second loop, there will be 2 moving pointers i.e. k(starts from j+1) and l(starts from the last index). The pointer k will move forward and the pointer l will move backward until they cross each other while the value of i and j will be fixed.
- Now we will check the sum i.e. nums[i]+nums[j]+nums[k]+nums[l].
- If the sum is greater, then we need lesser elements and so we will decrease the value of l.
- If the sum is lesser than the target, we need a bigger value and so we will increase the value of k.
- If the sum is equal to the target, we will simply insert the quad i.e. nums[i], nums[j], nums[k], and nums[l] into our answer and move the pointers k and l skipping the duplicate elements(i.e. by checking the adjacent elements while moving the pointers).
- Finally, we will have a list of unique quadruplets.
Note: For a better understanding of intuition, please watch the video at the bottom of the page.
Code
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size(); //size of the array
vector<vector<int>> ans;
// sort the given array:
sort(nums.begin(), nums.end());
//calculating the quadruplets:
for (int i = 0; i < n; i++) {
// avoid the duplicates while moving i:
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; j++) {
// avoid the duplicates while moving j:
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// 2 pointers:
int k = j + 1;
int l = n - 1;
while (k < l) {
long long sum = nums[i];
sum += nums[j];
sum += nums[k];
sum += nums[l];
if (sum == target) {
vector<int> temp = {nums[i], nums[j], nums[k], nums[l]};
ans.push_back(temp);
k++; l--;
//skip the duplicates:
while (k < l && nums[k] == nums[k - 1]) k++;
while (k < l && nums[l] == nums[l + 1]) l--;
}
else if (sum < target) k++;
else l--;
}
}
}
return ans;
}
int main()
{
vector<int> nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
int target = 9;
vector<vector<int>> ans = fourSum(nums, target);
cout << "The quadruplets are: \n";
for (auto it : ans) {
cout << "[";
for (auto ele : it) {
cout << ele << " ";
}
cout << "] ";
}
cout << "\n";
return 0;
}
import java.util.*;
public class tUf {
public static List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length; // size of the array
List<List<Integer>> ans = new ArrayList<>();
// sort the given array:
Arrays.sort(nums);
// calculating the quadruplets:
for (int i = 0; i < n; i++) {
// avoid the duplicates while moving i:
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; j++) {
// avoid the duplicates while moving j:
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// 2 pointers:
int k = j + 1;
int l = n - 1;
while (k < l) {
long sum = nums[i];
sum += nums[j];
sum += nums[k];
sum += nums[l];
if (sum == target) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
temp.add(nums[l]);
ans.add(temp);
k++;
l--;
// skip the duplicates:
while (k < l && nums[k] == nums[k - 1]) k++;
while (k < l && nums[l] == nums[l + 1]) l--;
} else if (sum < target) k++;
else l--;
}
}
}
return ans;
}
public static void main(String[] args) {
int[] nums = {4, 3, 3, 4, 4, 2, 1, 2, 1, 1};
int target = 9;
List<List<Integer>> ans = fourSum(nums, target);
System.out.println("The quadruplets are: ");
for (List<Integer> it : ans) {
System.out.print("[");
for (int ele : it) {
System.out.print(ele + " ");
}
System.out.print("] ");
}
System.out.println();
}
}
from typing import List
def fourSum(nums: List[int], target: int) -> List[List[int]]:
n = len(nums) # size of the array
ans = []
# sort the given array:
nums.sort()
# calculating the quadruplets:
for i in range(n):
# avoid the duplicates while moving i:
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n):
# avoid the duplicates while moving j:
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# 2 pointers:
k = j + 1
l = n - 1
while k < l:
_sum = nums[i] + nums[j] + nums[k] + nums[l]
if _sum == target:
temp = [nums[i], nums[j], nums[k], nums[l]]
ans.append(temp)
k += 1
l -= 1
# skip the duplicates:
while k < l and nums[k] == nums[k - 1]:
k += 1
while k < l and nums[l] == nums[l + 1]:
l -= 1
elif _sum < target:
k += 1
else:
l -= 1
return ans
if __name__ == '__main__':
nums = [4, 3, 3, 4, 4, 2, 1, 2, 1, 1]
target = 9
ans = fourSum(nums, target)
print("The quadruplets are:")
for it in ans:
print("[", end="")
for ele in it:
print(ele, end=" ")
print("]", end=" ")
print()
function majorityElement(v) {
let n = v.length; // size of the array
let cnt1 = 0, cnt2 = 0; // counts
let el1 = -Infinity; // element 1
let el2 = -Infinity; // element 2
// applying the Extended Boyer Moore's Voting Algorithm:
for (let i = 0; i < n; i++) {
if (cnt1 === 0 && el2 !== v[i]) {
cnt1 = 1;
el1 = v[i];
}
else if (cnt2 === 0 && el1 !== v[i]) {
cnt2 = 1;
el2 = v[i];
}
else if (v[i] === el1) cnt1++;
else if (v[i] === el2) cnt2++;
else {
cnt1--, cnt2--;
}
}
let ls = []; // list of answers
// Manually check if the stored elements in
// el1 and el2 are the majority elements:
cnt1 = 0, cnt2 = 0;
for (let i = 0; i < n; i++) {
if (v[i] === el1) cnt1++;
if (v[i] === el2) cnt2++;
}
let mini = Math.floor(n / 3) + 1;
if (cnt1 >= mini) ls.push(el1);
if (cnt2 >= mini) ls.push(el2);
// Uncomment the following line
// if it is told to sort the answer array:
// ls.sort(); // TC --> O(2*log2) ~ O(1);
return ls;
}
let arr = [11, 33, 33, 11, 33, 11];
let ans = majorityElement(arr);
console.log("The majority elements are: " + ans.join(" "));
Output:The quadruplets are: [1 1 3 4 ] [1 2 2 4 ] [1 2 3 3 ]
Complexity Analysis
Time Complexity: O(N3), where N = size of the array.
Reason: Each of the pointers i and j, is running for approximately N times. And both the pointers k and l combined can run for approximately N times including the operation of skipping duplicates. So the total time complexity will be O(N3).
Space Complexity: O(no. of quadruplets), This space is only used to store the answer. We are not using any extra space to solve this problem. So, from that perspective, space complexity can be written as O(1).
Video Explanation
Special thanks to Rishiraj Girmal, Sudip Ghosh and KRITIDIPTA GHOSH for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article