LeetCode #18 - 4 Sum
November 14, 2020
Hello happy people 👋! It’s time for another LeetCode problem.
Problem Statement
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.
Constraints:
- 0 ≤
nums.length≤ 200 - -109 ≤
nums[i]≤ 109 - -109 ≤
target≤ 109
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]]Example 2:
Input: nums = [], target = 0
Output: []Analysis
We have seen problems like this before — Two Sum, 3 Sum and 3 Sum Closest.
A simple way to solve 4 Sum problem is to reduce it to 3 Sum problem which can further be reduced to Two Sum problem. Therefore, here our aim is to find a combination of four numbers and all such combinations are unique.
Approach
The steps can be as follows —
- Sort the array in time O(n * log n).
- Now for each element
iandj, do the following steps — - Set two pointers left —
k = j + 1and right —l = n - 1. - Check if
nums[i] + nums[j] + nums[k] + nums[l] == targetand add it to the result, if true/ - If
nums[i] + nums[j] + nums[k] + nums[l] < target, then we are too left, and we need to move right so increment left pointer i.e.k++. - If
nums[i] + nums[j] + nums[k] + nums[l] > target, then we are too right, and we need to decrement the right pointer i.e.,l--.
Time Complexity
We are scanning the entire array keeping one element fixed and then doing it for another element fixed. We are doing this for every element in the array. Thus, we are scanning each element of array n number of times. And we are doing this for n times, hence the worst case time complexity will be O(n3 + n * log n) which comes down to O(n3).
Space Complexity
We are not using any data structure for the intermediate computations, hence the space complexity is O(1).
Code
Java
public class FourSum {
private static List<List<Integer>> fourSum(int[] nums, int target) {
// Resultant list
List<List<Integer>> quadruplets = new ArrayList<>();
// Base condition
if (nums == null || nums.length < 4) {
return quadruplets;
}
// Sort the array
Arrays.sort(nums);
// Length of the array
int n = nums.length;
// Loop for each element in the array
for (int i = 0; i < n - 3; i++) {
// Check for skipping duplicates
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// Reducing problem to 3Sum problem
for (int j = i + 1; j < n - 2; j++) {
// Check for skipping duplicates
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// Left and right pointers
int k = j + 1;
int l = n - 1;
// Reducing to two sum problem
while (k < l) {
int currentSum = nums[i] + nums[j] + nums[k] + nums[l];
if (currentSum < target) {
k++;
} else if (currentSum > target) {
l--;
} else {
quadruplets.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
k++;
l--;
// Check for skipping duplicates
while (k < l && nums[k] == nums[k - 1]) {
k++;
}
while (k < l && nums[l] == nums[l + 1]) {
l--;
}
}
}
}
}
return quadruplets;
}
}Python
def fourSum(nums: List[int], target: int) -> List[List[int]]:
# Resultant list
quadruplets = list()
# Base condition
if nums is None or len(nums) < 4:
return quadruplets
# Sort the array
nums.sort()
# Length of the array
n = len(nums)
# Loop for each element of the array
for i in range(0, n - 3):
# Check for skipping duplicates
if i > 0 and nums[i] == nums[i - 1]:
continue
# Reducing to three sum problem
for j in range(i + 1, n - 2):
# Check for skipping duplicates
if j != i + 1 and nums[j] == nums[j - 1]:
continue
# Left and right pointers
k = j + 1
l = n - 1
# Reducing to two sum problem
while k < l:
current_sum = nums[i] + nums[j] + nums[k] + nums[l]
if current_sum < target:
k += 1
elif current_sum > target:
l -= 1
else:
quadruplets.append([nums[i], nums[j], nums[k], nums[l]])
k += 1
l -= 1
while k < l and nums[k] == nums[k - 1]:
k += 1
while k < l and nums[l] == nums[l + 1]:
l -= 1
return quadrupletsJavaScript
var fourSum = function (nums, target) {
// Resultant list
const quadruplets = [];
// Base condition
if (nums == undefined || nums.length < 4) {
return quadruplets;
}
// Sort the array
nums.sort((a, b) => a - b);
// Length of the array
const n = nums.length;
// Loop for each element of the array
for (let i = 0; i < n - 3; i++) {
// Check for skipping duplicates
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// Reducing to three sum problem
for (let j = i + 1; j < n - 2; j++) {
// Check for skipping duplicates
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// Left and right pointers
let k = j + 1;
let l = n - 1;
// Reducing to two sum problem
while (k < l) {
const currentSum = nums[i] + nums[j] + nums[k] + nums[l];
if (currentSum < target) {
k++;
} else if (currentSum > target) {
l--;
} else {
quadruplets.push([nums[i], nums[j], nums[k], nums[l]]);
k++;
l--;
// Check for skipping duplicates
while (k < l && nums[k] == nums[k - 1]) {
k++;
}
while (k < l && nums[l] == nums[l + 1]) {
l--;
}
}
}
}
}
return quadruplets;
};Kotlin
fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
// Resultant list
val quadruplets: MutableList<List<Int>> = ArrayList()
// Base condition
if (nums.size < 4) {
return quadruplets
}
// Sort the array
Arrays.sort(nums)
// Length of the array
val n = nums.size
// Loop for each element in the array
for (i in 0 until n - 3) {
// Check for skipping duplicates
if (i > 0 && nums[i] == nums[i - 1]) {
continue
}
// Reducing problem to 3Sum problem
for (j in i + 1 until n - 2) {
// Check for skipping duplicates
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue
}
// Left and right pointers
var k = j + 1
var l = n - 1
// Reducing to two sum problem
while (k < l) {
val currentSum = nums[i] + nums[j] + nums[k] + nums[l]
when {
currentSum < target -> {
k++
}
currentSum > target -> {
l--
}
else -> {
quadruplets.add(listOf(nums[i], nums[j], nums[k], nums[l]))
k++
l--
// Check for skipping duplicates
while (k < l && nums[k] == nums[k - 1]) {
k++
}
while (k < l && nums[l] == nums[l + 1]) {
l--
}
}
}
}
}
}
return quadruplets
}Complete Code
Conclusion
Congratulations 👏! We have solved one more problem from LeetCode and it was extension of the few we solved 😃.
I hope you enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork 🔪 and star ⭐ it.
Till next time… Happy coding 😄 and Namaste 🙏!
