4Sum

Problem

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Similar Problem on Pramp

Your function should return an array of these numbers in an ascending order. If such a quadruplet doesn’t exist, return an empty array.

Note that there may be more than one quadruplet in arr whose sum is s. You’re asked to return the first one you encounter (considering the results are sorted).

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 = [2,2,2,2,2], target = 8
Output:
[[2,2,2,2]]

Solution

In 2Sum Problem, we had a problem with sorting as we could have solved hte problem in O(n) time using hashmap. But here we already have O(n^3) if we use hash. So, we can sort.

We can also use solutions like 3Sum - Classic Problem and 2Sum Problem as well.

Also, we can implement kSum Problem

Method 1 - Sorting

Algorithm

• Sort the array
• Run 1 outer loop from 0 to n-3
• Run inner loop from n-1 to 2
• Runner inner most loop using 2 pointers l and r, l = i+1, r=j-1
• Continue finding the quads till we are out of loops

Duplicates needs to handled.

Code

Java

public List<List<Integer>> fourSum(int[] nums, int target) {
	Arrays.sort(nums);
	List <List<Integer>> result = new ArrayList<>();
	int length = nums.length;

	if (length < 4) {
		return result;
	}

	for (int i = 0; i < length - 3; i++) {
		if (i != 0 && nums[i] == nums[i - 1]) {
			continue;
		}

		for (int j = length - 1; j >= 2; j--) {
			if (j != length - 1 && nums[j] == nums[j + 1]) {
				continue;
			}

			int l = i + 1;
			int r = j - 1;
			int cur = nums[i] + nums[j];
			int remainder = target - cur;

			while (l < r) {
				if (l != i + 1 && nums[l] == nums[l - 1]) {
					l++;
					continue;
				}

				if (r != j - 1 && nums[r] == nums[r + 1]) {
					r--;
					continue;
				}

				int temp = nums[l] + nums[r];

				if (temp == remainder) {
					result.add(List.of(nums[i], nums[l], nums[r], nums[j]));
					l++;
					r--;
				} else if (temp < remainder) {
					l++;
				} else {
					r--;
				}
			}
		}
	}

	return result;
}

Method 2 - Using kSum

We can use generic kSum Problem.

Code

Java

public List<List<Integer>> fourSum(int[] nums, int target) {
	return kSum(nums, target, 4);
}

Complexity

• ⏰ Time complexity: O(n^3)
• 🧺 Space complexity: O(1)