# LeetCode #18 - 4 Sum

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 β

1. Sort the array in time O(n * log n).
2. Now for each element i and j, do the following steps β
3. Set two pointers left β k = j + 1 and right β l = n - 1.
4. Check if nums[i] + nums[j] + nums[k] + nums[l] == target and add it to the result, if true/
5. 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++.
6. 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
// Base condition
if (nums == null || nums.length < 4) {
}
// 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 {
k++;
l--;
// Check for skipping duplicates
while (k < l && nums[k] == nums[k - 1]) {
k++;
}
while (k < l && nums[l] == nums[l + 1]) {
l--;
}
}
}
}
}
}
}

### Python

def fourSum(nums: List[int], target: int) -> List[List[int]]:
# Resultant list
# Base condition
if nums is None or len(nums) < 4:
# 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:
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 quadruplets

### JavaScript

var fourSum = function (nums, target) {
// Resultant list
// Base condition
if (nums == undefined || nums.length < 4) {
}
// 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 {
k++;
l--;
// Check for skipping duplicates
while (k < l && nums[k] == nums[k - 1]) {
k++;
}
while (k < l && nums[l] == nums[l + 1]) {
l--;
}
}
}
}
}
};

### Kotlin

fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
// Resultant list
// Base condition
if (nums.size < 4) {
}
// 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 -> {
k++
l--
// Check for skipping duplicates
while (k < l && nums[k] == nums[k - 1]) {
k++
}
while (k < l && nums[l] == nums[l + 1]) {
l--
}
}
}
}
}
}
}