4 Sum LeetCode Solution is an engaging programming challenge that gives you an opportunity to flex your optimization and problem-solving muscles. In this in-depth tutorial, we will cover various approaches to finding the 4 Sum leetcode problem solution along with examples, code, and explanations so you can master the concepts behind this frequently encountered problem.
Introduction to 4 Sum Leetcode Problem
Problem Statement
Given an array nums of n integers and an integer target, are there four 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.
Example
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
Approach & Algorithm
Optimized Approach (Sorting & Two Pointers)
Explanation:
Before diving into the optimized solution for the 4 Sum leetcode problem, let’s familiarize ourselves with the various techniques that are commonly applied. The most efficient approach for solving this problem combines the sorting algorithm or sorted array and two pointers strategy.
First, sort the array nums. Then, iterate through the array using two nested loops (i.e., i and j). For each pair of (i, j), find all pairs (k, l) such that nums[i] + nums[j] + nums[k] + nums[l] = target using the two pointers method. Now, to avoid duplicates, skip the elements that are equal to their previous element.
Finally, return the resulting list of quadruplets.
Pseudocode:
1. Sort array nums of n integers
2. For i in 0 to (length of nums - 3):
a. If i > 0 and nums[i] == nums[i - 1], continue to next iteration
b. For j in (i + 1) to (length of nums - 2):
- If j > i + 1 and nums[j] == nums[j - 1], continue to next iteration
- Initialize two pointers: k = j + 1, l = length of nums - 1
- While k < l:
+ Calculate the current_sum = nums[i] + nums[j] + nums[k] + nums[l]
+ If current_sum == target:
* Add the quadruplet to the result
* Increment k, while ensuring nums[k] != nums[k - 1] for unique values
* Decrement l, while ensuring nums[l] != nums[l + 1] for unique values
+ Else if current_sum > target, decrement l
+ Else increment k
3. Return the result
Complexity analysis:
The time complexity of this optimized approach is O(N^3) and space complexity is O(N) for the additional space required to store the resulting quadruplets.
Detailed 4 Sum LeetCode Solution in C, C++, Python, Java
4 Sum Leetcode Solution C
#include <stdio.h>
#include <stdlib.h>
int* sort_array(int* nums, int numsSize) {
for (int i = 0; i < numsSize - 1; i++) {
for (int j = 0; j < numsSize - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
return nums;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
// Sort the input array
nums = sort_array(nums, numsSize);
*returnSize = 0;
/* Allocate memory for the result */
int **result = (int**)malloc(numsSize * numsSize * sizeof(int*));
*returnColumnSizes = (int*)calloc(numsSize * numsSize, sizeof(int));
for (int i = 0; i < numsSize - 3; i++) {
// Skip duplicate elements
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < numsSize - 2; j++) {
// Skip duplicate elements
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = numsSize - 1;
while (k < l) {
int current_sum = nums[i] + nums[j] + nums[k] + nums[l];
if (current_sum == target) {
result[*returnSize] = (int*)malloc(4 * sizeof(int));
result[*returnSize][0] = nums[i];
result[*returnSize][1] = nums[j];
result[*returnSize][2] = nums[k];
result[*returnSize][3] = nums[l];
(*returnColumnSizes)[*returnSize] = 4;
(*returnSize)++;
// Skip duplicate elements
while (k < l && nums[k] == nums[k + 1]) k++;
while (k < l && nums[l] == nums[l - 1]) l--;
k++;
l--;
} else if (current_sum > target) {
l--;
} else {
k++;
}
}
}
}
return result;
}
4 Sum Leetcode Solution C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int n = nums.size();
if (n < 4) return result;
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 - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = n - 1;
while (k < l) {
int current_sum = nums[i] + nums[j] + nums[k] + nums[l];
if (current_sum == target) {
result.push_back({nums[i], nums[j], nums[k], nums[l]});
while (k < l && nums[k] == nums[k + 1]) k++;
while (k < l && nums[l] == nums[l - 1]) l--;
k++; l--;
} else if (current_sum > target) {
l--;
} else {
k++;
}
}
}
}
return result;
}
};
4 Sum Leetcode Solution Python
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
result = []
for i in range(len(nums) - 3):
if i > 0 and nums[i] == nums[i - 1]: continue
for j in range(i + 1, len(nums) - 2):
if j > i + 1 and nums[j] == nums[j - 1]: continue
k, l = j + 1, len(nums) - 1
while k < l:
current_sum = nums[i] + nums[j] + nums[k] + nums[l]
if current_sum == target:
result.append([nums[i], nums[j], nums[k], nums[l]])
while k < l and nums[k] == nums[k + 1]: k += 1
while k < l and nums[l] == nums[l - 1]: l -= 1
k += 1; l -= 1
elif current_sum > target:
l -= 1
else:
k += 1
return result
4 Sum Leetcode Solution Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int k = j + 1, l = nums.length - 1;
while (k < l) {
int current_sum = nums[i] + nums[j] + nums[k] + nums[l];
if (current_sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
while (k < l && nums[k] == nums[k + 1]) k++;
while (k < l && nums[l] == nums[l - 1]) l--;
k++; l--;
} else if (current_sum > target) {
l--;
} else {
k++;
}
}
}
}
return result;
}
}Conclusion
The 4 Sum leetcode solution discussed in this article utilizes an optimized approach involving sorting and two pointers. By learning how to implement the algorithm in various programming languages like C, C++, Python, and Java, you are now well-equipped to tackle similar problems efficiently. Remember to be mindful of your choice of optimization techniques and handling edge cases to always stay ahead in your programming endeavors. Happy coding!
