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 < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
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]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
Problem Description
The problem at hand asks us to find all unique combinations of four numbers within a given array, such that the sum of these four numbers equals a specified target value. To clarify with an example, if the input array is [1, 0, -1, 0, -2, 2] and the target is 0, one possible quadruplet that sums up to the target would be [-1, 0, 0, 1]. Note the following constraints that we must adhere to:
- Indices
a,b,c, anddare each unique; no index is reused for the same quadruplet. - The elements at these indices must sum up to the given target value.
- We are to return a list of all such unique quadruplets, and the order of quadruplets does not matter.
This problem is an extension of the classic “two sum” and “three sum” problems where instead of finding pairs or triplets with a sum equal to the target, we are finding quadruplets.
Intuition
The solution adopts a methodical approach by iterating through the array in a nested manner, akin to the “three sum” problem but with an additional layer for the fourth number. Here’s a breakdown of the approach:
- First, we sort the array. This step is crucial as it allows us to efficiently avoid duplicates and use the two-pointer technique to find pairs that sum up to a specific value.
- We initialize a list to hold the solutions.
- We iterate through the array with two pointers, selecting the first two numbers of the possible quadruplet.
- For each unique pair (the first two numbers), we apply the two-pointer technique to the remainder of the array to find the next two numbers that complete the quadruplet, ensuring their sum equals the target.
- While iterating with the third and fourth pointers (within the sorted remainder of the array), we move the pointers inward until they meet to find pairs that sum up to the complement of the target minus the first two numbers.
- When the sum of the quadruplet equals the target, we add it to our solution list. We then skip over any duplicate numbers to avoid repeating the same quadruplet in our solution.
This approach ensures that each possible unique pair is considered, while the sorting and skipping duplicates prevent us from including repeated quadruplets. Though the time complexity seems nominally high at O(n3)O(n3), where n is the number of elements in the input array, sorting and early termination when possible make the solution practical enough for moderately sized arrays.
The space complexity is stated to be O(logn)O(logn), which generally refers to the space used by the sorting algorithm under the hood, as the space needed for the output does not count towards the space complexity of the algorithm itself.
Solution Approach
The implementation of the solution employs the following algorithms, data structures, and patterns:
- Sorting: The
numsarray is initially sorted to enable a straightforward check for duplicates and use the two-pointer technique efficiently. Sorting brings elements in a non-decreasing order, which is vital for the subsequent steps. - Two-pointer Technique: This pattern is extensively used to find two elements in the sorted part of the array that sum up to a specific value. By moving two pointers inward from the outermost elements, we can quickly determine if the current pair is too large (in which case we move the right pointer left) or too small (moving the left pointer right).
- Nested Loops:
- The first loop runs through the array, starting from the first element up to the third-to-last, selecting the first element of a potential quadruplet.
- The second nested loop starts from the element right after the first one up to the second-to-last, selecting the second element of the quadruplet.
- Skipping duplicates:
- After the first number is chosen, if it is the same as the number before it, we skip the current iteration to avoid duplicates in the first position of quadruplets.
- The same duplicate check is done for the second number in the quadruplet.
- Duplication checks are also applied after finding a valid quadruplet and moving the third and fourth pointers.
- Third and Fourth Pointers: After fixing the first two elements, two additional pointers (index
kandl) are used to find the last two elements of the quadruplet by moving them towards each other until they meet. - Checking for Quadruplets:
- A while loop is used to iterate through the array by moving the third and fourth pointers, testing if the sum of the elements at these four indices equals the target. If it does, a quadruplet is found and added to the
anslist. - If the sum is less than the target, this implies that we need a larger sum to reach the target, thus the third pointer (
k) is incremented. - If the sum is greater than the target, it implies we need a smaller sum, so the fourth pointer (
l) is decremented.
- A while loop is used to iterate through the array by moving the third and fourth pointers, testing if the sum of the elements at these four indices equals the target. If it does, a quadruplet is found and added to the
- Maintaining Uniqueness: After adding the found quadruplet to the
anslist, the third and fourth pointers are moved while skipping over any duplicates to maintain uniqueness in theanslist.
In summary, this methodical approach of looping and two-pointer technique, aided by sort and duplicate checks, is how the described solution achieves its goal of finding all unique quadruplets in the array that sum up to the target. The algorithms and patterns used reflect a well-considered approach that strikes a balance between correctness and efficiency.
Example Walkthrough
Let’s use a small example to illustrate the solution approach described. Consider an input array nums = [2, 1, 0, -1, -2] and a target value target = 0. Following the steps mentioned in the Intuition and Solution Approach sections, we aim to find all unique quadruplets in nums which sum up to target.
- Sorting: First, we sort the
numsarray which becomes[-2, -1, 0, 1, 2]. - Initialization: We initialize an empty list
ansto store the unique quadruplets. - Nested Loops:
- Start the first loop with index
i, which runs through the array from index 0 to 2 (inclusive as we need at least four numbers for a quadruplet). - Start the second loop with index
j, which runs through the array starting right after indexiup to index 3, to avoid overlap and ensure four unique indices.
- Start the first loop with index
- Skipping Duplicates: If we encounter any element at index
iorjthat is the same as the previous one, we skip to the next iteration to avoid duplicate quadruplets. - Third and Fourth Pointers: For each pair of indices
iandj, we set pointersk = j + 1andl = len(nums) - 1. In our example, supposei = 0andj = 1, thenkwill start at 2 andlwill start at 4. - Creating the Quadruplets:
- We use a
whileloop to iterate with pointerskandl. For our example, withk = 2andl = 4, we check ifnums[i] + nums[j] + nums[k] + nums[l]is equal to the target. So,(-2) + (-1) + 0 + 2 = -1, which is not equal to the target 0, hence we continue. - Because the sum is less than the target, we need to increase it. Thus, we move
kto the right (since the array is sorted, the next number will be larger). - On the next iteration,
k = 3andl = 4. The sum(-2) + (-1) + 1 + 2 = 0which matches the target. We add the quadruplet[-2, -1, 1, 2]to ouranslist.
- We use a
- Maintaining Uniqueness: Next, we move both
kandlto new positions while skipping duplicates to ensure we don’t record the same quadruplet again.
Iterating through rest of the array using this approach will examine all possible quadruplet combinations. The final ans list holds all unique valid quadruplets which in this example only includes [-2, -1, 1, 2].
Solution Implementation
class Solution {
public:
// Helper function to find two sum pairs given a target and current numbers
void findTwoSumPairs(vector<int>& nums, long long left, long long target, long long size,
vector<vector<int>> &result, long long firstNum, long long secondNum) {
long long right = size - 1;
// Iterate with two pointers approach
while (left < right) {
long long currentSum = nums[left] + nums[right];
// If current sum is too large, move the right pointer left
if (currentSum > target) {
right--;
}
// If current sum is too small, move the left pointer right
else if (currentSum < target) {
left++;
}
// If we found a valid pair, add it to result
else {
result.push_back({nums[left], nums[right], (int)secondNum, (int)firstNum});
// Skip duplicate values on both ends
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++; // Move the left pointer
right--; // Move the right pointer
}
}
}
// Helper function to find three sum pairs given the target and first number
void findThreeSumPairs(vector<int>& nums, long long target, long long start,
vector<vector<int>> &result, long long firstNum) {
long long size = nums.size();
// Iterate through each number and find valid pairs using two sum approach
for (long long i = start; i < size - 2; i++) {
// Skip duplicates to avoid repeated results
if (i > start && nums[i] == nums[i - 1]) continue;
// Find the remaining target for two sum search
long long remainingTarget = target - nums[i];
findTwoSumPairs(nums, i + 1, remainingTarget, size, result, firstNum, nums[i]);
}
}
// Main function to find all unique quadruplets that sum up to the target
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end()); // Sort the array to handle duplicates efficiently
// Iterate through each number and find three sum pairs
for (long long i = 0; i < nums.size(); i++) {
// Skip duplicate values to avoid repeated quadruplets
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Calculate remaining target after choosing the first number
long long remainingTarget = target - nums[i];
findThreeSumPairs(nums, remainingTarget, i + 1, result, nums[i]);
}
return result; // Return all found quadruplets
}
};Copied!
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
// Initialize the result list to store valid quadruplets
List<List<Integer>> li = new ArrayList<>();
// If input is invalid or array size is less than 4, return an empty list
if (nums == null || nums.length < 4) {
return li;
}
// Sort the array to simplify the process of finding unique quadruplets
Arrays.sort(nums);
// Iterate through the array, considering the first number of the quadruplet
for (int i = 0; i < nums.length - 3; i++) {
// Skip duplicates for the first number to avoid repeated results
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// Iterate through the array, considering the second number of the quadruplet
for (int j = i + 1; j < nums.length - 2; j++) {
// Skip duplicates for the second number
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// Initialize two pointers for the third and fourth numbers
int left = j + 1;
int right = nums.length - 1;
// Use the two pointers to find pairs that sum to the target
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
// If the sum matches the target, add the quadruplet to the result list
if (sum == target) {
li.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// Skip duplicate values for the third number
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// Skip duplicate values for the fourth number
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
// Move the pointers inward to continue searching
left++;
right--;
}
// If the sum is less than the target, move the left pointer to the right
else if (sum < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
}
}
// Return the list of quadruplets that sum up to the target
return li;
}
}Copied!
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
# Sort the input array to simplify the process of finding quadruplets
nums.sort()
res = [] # Initialize the result list to store valid quadruplets
# Iterate through the array to consider the first number of the quadruplet
for i in range(len(nums) - 3):
# Skip duplicate values for the first number to avoid repeated results
if i > 0 and nums[i] == nums[i - 1]:
continue
# Iterate through the array to consider the second number of the quadruplet
for j in range(i + 1, len(nums) - 2):
# Skip duplicate values for the second number
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# Use two pointers to find pairs that sum up to the target
left, right = j + 1, len(nums) - 1
# Continue searching while left pointer is less than right pointer
while left < right:
# Calculate the sum of the four numbers
four_sum = nums[i] + nums[j] + nums[left] + nums[right]
# If the sum matches the target, add the quadruplet to the result list
if four_sum == target:
res.append([nums[i], nums[j], nums[left], nums[right]])
left += 1 # Move the left pointer to the right
right -= 1 # Move the right pointer to the left
# Skip duplicate values for the third number (left pointer)
while left < right and nums[left] == nums[left - 1]:
left += 1
# Skip duplicate values for the fourth number (right pointer)
while left < right and nums[right] == nums[right + 1]:
right -= 1
# If the sum is less than the target, move the left pointer to the right
elif four_sum < target:
left += 1
# If the sum is greater than the target, move the right pointer to the left
else:
right -= 1
# Return the list of quadruplets that sum up to the target
return resCopied!
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
// Comparison function for sorting the array in ascending order
int compare(const void* a, const void *b) {
return (*(int*)a - *(int*)b);
}
// Function to find all unique quadruplets in the array that sum up to the target
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
int** ans = NULL; // Initialize the result array to store quadruplets
*returnSize = 0; // Initialize the return size to 0
// Sort the array to enable easy skipping of duplicates and to apply two-pointer technique
qsort(nums, numsSize, sizeof(int), compare);
// Iterate over the array to pick the first number of the quadruplet
for (int i = 0; i < numsSize - 3; i++) {
// Skip duplicates for the first number
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Iterate over the array to pick the second number of the quadruplet
for (int j = i + 1; j < numsSize - 2; j++) {
// Skip duplicates for the second number
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
// Compute the new target after picking the first two numbers
long long newTarget = (long long)target - nums[i] - nums[j];
// Set up two pointers to find the remaining two numbers
int low = j + 1, high = numsSize - 1;
while(low < high) {
long long sum = (long long)nums[low] + nums[high];
// If the sum is less than the new target, move the left pointer to the right
if(sum < newTarget) {
low++;
}
// If the sum is greater than the new target, move the right pointer to the left
else if (sum > newTarget) {
high--;
}
// If the sum equals the new target, add the quadruplet to the result
else {
(*returnSize)++; // Increment the return size
ans =(int**)realloc(ans, (*returnSize) * sizeof(int*)); // Resize the result array to accommodate the new quadruplet
ans[*returnSize - 1] = (int*)malloc(4 * sizeof(int*)); // Allocate memory for the new quadruplet
ans[*returnSize - 1][0] = nums[i]; // First number of the quadruplet
ans[*returnSize - 1][1] = nums[j]; // Second number of the quadruplet
ans[*returnSize - 1][2] = nums[low]; // Third number of the quadruplet
ans[*returnSize - 1][3] = nums[high]; // Fourth number of the quadruplet
// Skip duplicates for the third number (left pointer)
while(low < high && nums[low] == nums[low + 1]) low++;
// Skip duplicates for the fourth number (right pointer)
while(low < high && nums[high] == nums[high - 1]) high--;
low++; // Move the left pointer to the right
high--; // Move the right pointer to the left
}
}
}
}
// Allocate memory for the column sizes array
*returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));
// Set all column sizes to 4, since each quadruplet has 4 numbers
for(int i = 0; i < *returnSize; i++) {
(*returnColumnSizes)[i] = 4;
}
return ans; // Return the array of quadruplets
}Copied!
public class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
var result = new List<IList<int>>(); // Initialize a list to store the result quadruplets
Array.Sort(nums); // Sort the array to enable the two-pointer technique and handle duplicates
// Loop through the array to select the first number of the quadruplet
for (var k = 0; k < nums.Length - 3; k++) {
// Skip duplicate first numbers to avoid duplicate quadruplets
if (k > 0 && nums[k] == nums[k - 1]) continue;
// Loop through the array to select the second number of the quadruplet
for (var i = k + 1; i < nums.Length - 2; i++) {
// Skip duplicate second numbers to avoid duplicate quadruplets
if (i > k + 1 && nums[i] == nums[i - 1]) continue;
// Calculate the remaining sum required for the third and fourth numbers
long toFind = (long)target - (nums[i] + nums[k]);
// Set up two pointers for the third and fourth numbers
var lo = i + 1;
var hi = nums.Length - 1;
// Use two-pointer technique to find the third and fourth numbers
while (lo < hi) {
long sum = nums[lo] + nums[hi];
// If the sum of the third and fourth numbers equals the remaining target, add to the result
if (sum == toFind) {
result.Add(new List<int> {nums[k], nums[i], nums[lo], nums[hi]});
// Skip duplicate third numbers
while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
// Skip duplicate fourth numbers
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
}
// If the sum is less than the target, move the left pointer to the right
if (sum <toFind)
lo++;
// If the sum is greater than the target, move the right pointer to the left
else
hi--;
}
}
}
// Return the list of all unique quadruplets found
return result;
}
}Copied!
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const result = []; // Initialize the result array to store the quadruplets
// If there are less than 4 numbers, it's impossible to find a quadruplet
if (nums == null || nums.length < 4) {
return result;
}
// Sort the array to enable easy skipping of duplicates and to use two-pointer technique
nums.sort((a, b) => a - b);
const len = nums.length;
// Iterate through the array to pick the first number of the quadruplet
for (let i = 0; i < len - 3; i++) {
// Skip duplicates for the first number
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
// Iterate through the array to pick the second number of the quadruplet
for (let j = i+1; j < len - 2; j++) {
// Skip duplicates for the second number
if (j > i+1 && nums[j] == nums[j-1]) {
continue;
}
// Use two pointers to find the remaining two numbers
let left = j + 1;
let right = len - 1;
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right];
// If the sum equals the target, store the quadruplet
if (sum == target) {
result.push([nums[i], nums[j], nums[left], nums[right]]);
// Skip duplicate values for the third number (left pointer)
while (left < right && nums[left] == nums[left+1]) {
left++;
}
// Skip duplicate values for the fourth number (right pointer)
while (left < right && nums[right] == nums[right-1]) {
right--;
}
// Move both pointers inward to search for new pairs
left++;
right--;
}
// If the sum is smaller than the target, move the left pointer to the right
else if (sum < target) {
left++;
}
// If the sum is larger than the target, move the right pointer to the left
else {
right--;
}
}
}
}
// Return the list of quadruplets that sum up to the target
return result;
};Copied!
function fourSum(nums: number[], target: number): number[][] {
// Sort the input array to enable the two-pointer technique and handle duplicates
nums.sort((a, b) => a - b);
// Initialize an array to store the results (valid quadruplets)
const sums: Array<[number, number, number, number]> = [];
// Iterate through the array to select the first number (i)
for (let i = 0; i < nums.length - 3; i++) {
// Skip duplicate first numbers to avoid repeating the same quadruplet
if (nums[i - 1] === nums[i]) {
continue;
}
// Iterate through the array to select the second number (j)
for (let j = i + 1; j < nums.length - 2; j++) {
// Skip duplicate second numbers to avoid repeating the same quadruplet
if (j - i > 1 && nums[j - 1] === nums[j]) {
continue;
}
// Initialize two pointers for the third and fourth numbers (k and l)
let k = j + 1;
let l = nums.length - 1;
// Use the two-pointer technique to find the third and fourth numbers
while (k < l) {
const sum = nums[i] + nums[j] + nums[k] + nums[l];
// If the sum is less than the target, move the left pointer (k) to the right
if (sum < target) {
do { k++ } while (nums[k - 1] === nums[k]); // Skip duplicate numbers at position k
}
// If the sum is greater than the target, move the right pointer (l) to the left
else if (sum > target) {
do { l-- } while (nums[l] === nums[l + 1]); // Skip duplicate numbers at position l
}
// If the sum is equal to the target, add the quadruplet to the result list
else {
sums.push([nums[i], nums[j], nums[k], nums[l]]);
// Skip duplicate numbers after finding a valid quadruplet
do { k++ } while (nums[k - 1] === nums[k]);
do { l-- } while (nums[l] === nums[l + 1]);
}
}
}
}
// Return the list of all unique quadruplets
return sums;
}Copied!
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[][]
*/
function fourSum($nums, $target) {
// Initialize an empty array to store the result
$result = [];
// If there are fewer than 4 numbers, return an empty result
if (count($nums) < 4) return $result;
// Sort the input array to make it easier to avoid duplicates and apply two-pointer technique
sort($nums);
$n = count($nums);
// Loop through the array for the first number (i)
for ($i = 0; $i < $n - 3; $i++) {
// Skip duplicate first numbers to avoid repeating the same quadruplet
if ($i > 0 && $nums[$i] == $nums[$i - 1]) continue;
// Loop through the array for the second number (j)
for ($j = $i + 1; $j < $n - 2; $j++) {
// Skip duplicate second numbers to avoid repeating the same quadruplet
if ($j > $i + 1 && $nums[$j] == $nums[$j - 1]) continue;
// Initialize two pointers for the third and fourth numbers (k and l)
$k = $j + 1;
$l = $n - 1;
// Use the two-pointer technique to find the third and fourth numbers
while ($k < $l) {
$sum = $nums[$i] + $nums[$j] + $nums[$k] + $nums[$l];
// If the sum is less than the target, move the left pointer (k) to the right
if ($sum < $target) {
$k++;
}
// If the sum is greater than the target, move the right pointer (l) to the left
elseif ($sum > $target) {
$l--;
}
// If the sum is equal to the target, add the quadruplet to the result
else {
$result[] = [$nums[$i], $nums[$j], $nums[$k], $nums[$l]];
// Move both pointers to avoid duplicates
$k++;
$l--;
// Skip duplicate third numbers (k)
while ($k < $l && $nums[$k] == $nums[$k - 1]) $k++;
// Skip duplicate fourth numbers (l)
while ($k < $l && $nums[$l] == $nums[$l + 1]) $l--;
}
}
}
}
// Return the result with all unique quadruplets
return $result;
}
}Copied!
class Solution {
// Function to find all unique quadruplets that sum up to the target value
func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let len = nums.count
// If there are fewer than 4 elements, it's impossible to form a quadruplet
guard len >= 4 else { return [] }
var result = [[Int]]()
// Sort the input array to make it easier to avoid duplicates and apply two-pointer technique
let sort = nums.sorted()
// Loop through the array for the first number (a)
for a in 0..<(len - 1) where a == 0 || sort[a] != sort[a-1] {
// Loop through the array for the second number (b)
for b in (a + 1)..<len where b == a + 1 || sort[b] != sort[b-1] {
var c = b + 1, d = len - 1
// Use two-pointer technique for the third (c) and fourth (d) numbers
while c < d {
let val = (a: sort[a], b: sort[b], c: sort[c], d: sort[d])
let sum = (val.a + val.b + val.c + val.d)
// If the sum equals the target, add the quadruplet to the result
if sum == target { result.append([val.a,val.b,val.c,val.d]) }
// If the sum is less than the target, move the left pointer (c) to the right
if sum < target {
// Skip duplicate values for the third number (c)
while sort[c] == val.c, c < d { c += 1 }
}
// If the sum is greater than the target, move the right pointer (d) to the left
else {
// Skip duplicate values for the fourth number (d)
while sort[d] == val.d, d > b { d -= 1 }
}
}
}
}
// Return the result with all unique quadruplets
return result
}
}Copied!
class Solution {
// List to store the results (unique quadruplets)
val rtnVal: ArrayList<List<Int>> = arrayListOf()
// Set to track already processed combinations to avoid duplicates
val existing: HashSet<Long> = hashSetOf<Long>()
fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
// If the array size is exactly 4, check if the sum of all elements equals the target
if (nums.size == 4) {
var sum: Long = 0L
for (i in 0 .. 3) {
sum += nums[i].toLong()
}
// If the sum matches the target, add the quadruplet to results
if (sum == target.toLong()) {
rtnVal.add(listOf(nums[0], nums[1], nums[2], nums[3]))
}
return rtnVal.toList()
}
// Sort the array to allow easier checking of potential quadruplets
Arrays.sort(nums)
val longTarget = target.toLong()
// Iterate through the array, looking for potential pairs
for (i in 0 .. nums.size - 3) {
// Skip duplicate values for i
if (i > 0 && nums[i-1] == nums[i]) {
continue
}
for (j in i+1 .. nums.size - 2) {
// Skip duplicate values for j
if (j > i+1 && nums[j-1] == nums[j]) {
continue
}
// Call the helper function to perform the two-pointer scan
leftRightScan(nums, longTarget, i, j)
}
}
// This line was likely added for performance improvement but has no impact on functionality
val x = 6 // This made LeetCode think it was faster. 8^/
// Return the list of unique quadruplets found
return rtnVal.toList()
}
// Helper function to scan for valid quadruplets using two pointers
private fun leftRightScan(nums: IntArray, target: Long, i: Int, j: Int) {
var ptrLeft: Int = j + 1
var ptrRight: Int = nums.size - 1
// Perform the two-pointer technique to find the sum of four elements
while (ptrLeft < ptrRight) {
val sum = nums[i].toLong() + nums[j].toLong() +
nums[ptrLeft].toLong() + nums[ptrRight].toLong()
// Move pointers based on the sum comparison with the target
if (sum < target) {
ptrLeft ++
} else if (sum > target) {
ptrRight --
} else {
// Create a unique key for this quadruplet to avoid duplicates
val key: Long = makeKey(
nums[i], nums[j], nums[ptrLeft]
)
// If the key hasn't been encountered before, add the quadruplet to the result
if (! existing.contains(key)) {
rtnVal.add(listOf(
nums[i], nums[j], nums[ptrLeft], nums[ptrRight])
)
existing.add(key) // Mark this quadruplet as processed
}
// Move the pointers inward to check for other combinations
ptrLeft++
ptrRight--
}
}
}
// Helper function to generate a unique key for a combination of three numbers
private fun makeKey(i: Int, j: Int, pl: Int): Long {
return i.toLong() + (j.toLong() * 1_000_000L) +
(pl.toLong() * 1_000_000L * 1_000_000L)
}
}Copied!
class Solution {
// Method to find all unique quadruplets that sum up to the target
List<List<int>> fourSum(List<int> nums, int target) {
List<List<int>> result = [];
// Sort the input array to make it easier to find quadruplets and skip duplicates
nums.sort();
int first = 0;
// Print the sorted array for debugging purposes
print(nums);
// Keep removing the first element and find pairs that sum up to the target
while(nums.length > 3) {
// Remove the first element for each outer loop iteration
first = nums.removeAt(0);
// Iterate through the array starting from index 0
for (int i = 0; i < nums.length; i++) {
int right = nums.length - 1; // Right pointer starts at the end of the array
int left = i + 1; // Left pointer starts after the current index
// Two-pointer approach to find a pair that, along with `first` and `nums[i]`, sums to the target
while (left < right) {
// Calculate the sum of the current quadruplet (first, nums[left], nums[right], nums[i])
int sum = first + nums[left] + nums[right] + nums[i];
// If sum equals the target, we have found a valid quadruplet
if (sum == target) {
// Create a temporary list for the quadruplet and sort it
final to = [nums[left], nums[right], nums[i], first];
to.sort(); // Sorting to ensure uniqueness, as we need to compare elements in sorted order
// Check if the quadruplet already exists in the result list, to avoid duplicates
if (result
.where((element) =>
element[0] == to[0] &&
element[1] == to[1] &&
element[2] == to[2] &&
element[3] == to[3])
.isEmpty) {
// If not, add it to the result list
result.add(to);
}
// Move the left pointer to the right, skipping over duplicates
left++;
while(nums[left] == nums[left-1] && left < right) {
left++;
}
}
// If sum is greater than target, move the right pointer to the left
else if (sum > target) {
right--;
}
// If sum is less than target, move the left pointer to the right
else if (sum < target) {
left++;
}
}
}
}
// Return the list of unique quadruplets found
return result;
}
}Copied!
// Define a type for a pair (2 integers)
type dplet [2]int
// Define a type for a quadruple (4 integers)
type qplet [4]int
// Main function to find all unique quadruplets that sum to the target
func fourSum(nums []int, target int) [][]int {
// Calculate all pair sums and store their indices
sums := calcPairSums(nums)
// Map to track already visited quadruplets to avoid duplicates
visited := make(map[qplet]bool)
// Result list to store the final list of unique quadruplets
var result [][]int
// Create a list of all pair sums to iterate over
allSums := make([]int, 0, len(sums))
// Populate the allSums array with all pair sums
for sum, _ := range sums {
allSums = append(allSums, sum)
}
// Iterate over each pair sum
for i := 0; i < len(allSums); i++ {
sum := allSums[i]
// Get the pairs that make up the current sum
pairs := sums[sum]
// Calculate the difference between the target and current sum
diff := target - sum
// Get the pairs that make up the difference
pairs2 := sums[diff]
// If there are no pairs that sum up to the difference, skip
if len(pairs2) == 0 {
continue
}
// Label to break out of nested loop if necessary
pairsLoop:
// Loop over the first set of pairs
for _, p1 := range pairs {
// Loop over the second set of pairs
for _, p2 := range pairs2 {
// Skip if the pairs overlap or are the same
if checkSelfDuplicate(p1, p2) {
continue
}
// Create a quadruplet using the pair indices and corresponding nums values
p := makeQplet(p1, p2, nums)
// If the quadruplet has been visited, skip it
if visited[p] {
continue
}
// Mark the quadruplet as visited
visited[p] = true
// Add the quadruplet to the result list
result = append(result, p[:])
// If sum and diff are equal, break out of the pairs loop to prevent duplicate pairs
if sum == diff {
break pairsLoop
}
}
}
// Once done with the current diff, remove it from the sums map
delete(sums, diff)
}
// Return the list of unique quadruplets
return result
}
// Function to calculate all pair sums and store the indices of the pairs
func calcPairSums(nums []int) map[int][]dplet {
// Initialize a map to store the sums and corresponding indices as pairs
sums := make(map[int][]dplet)
// Iterate through the array to calculate all possible pair sums
for i := 0; i < len(nums); i++ {
n1 := nums[i]
// For each element, find pairs with subsequent elements
for j := i + 1; j < len(nums); j++ {
n2 := nums[j]
// Store the pair sum and the indices in the sums map
sums[n1+n2] = append(sums[n1+n2], makeDplet(i, j, nums))
}
}
// Return the map of pair sums and their corresponding indices
return sums
}
// Helper function to create a dplet (pair of indices) from two numbers
func makeDplet(i, j int, nums []int) dplet {
// Ensure the pair is always ordered by the smaller value first
if nums[i] > nums[j] {
return dplet{j, i}
}
return dplet{i, j}
}
// Helper function to create a qplet (quadruplet) from two pairs
func makeQplet(d1, d2 dplet, nums []int) qplet {
var first, second dplet
// Determine the correct order of the two pairs based on the first element
if nums[d1[0]] > nums[d2[0]] {
first, second = d2, d1
} else {
first, second = d1, d2
}
// Create the quadruplet by adding the elements in the correct order
var result qplet
for i := 0; i < 2; i++ {
result[i] = nums[first[i]]
result[i+2] = nums[second[i]]
}
// Sort the quadruplet to ensure uniqueness by ordering the elements
for i := 2; i < 4; i++ {
if result[i-1] > result[i] {
result[i-1], result[i] = result[i], result[i-1]
}
}
// Return the resulting quadruplet
return result
}
// Helper function to check if two pairs have any common elements (i.e., duplicates)
func checkSelfDuplicate(p1, p2 dplet) bool {
// Check if any element from the two pairs are the same
return p1[0] == p2[0] || p1[1] == p2[1] || p1[0] == p2[1] || p1[1] == p2[0]
}Copied!
Time and Space Complexity
The provided code implements the four number sum problem (4Sum), which is an extension of the 3Sum problem. The algorithm searches for all unique quadruplets in an array that sum up to a given target. Here’s an analysis of its time complexity and space complexity:
Time Complexity
The time complexity of the code is O(n^3), where n is the number of elements in the array. Here’s the breakdown:
- The code starts with sorting the input array, which is
O(n log n)using a typical sorting algorithm like quicksort or mergesort. - Next, there are two nested loops iterating through the array.
- The outer loop (index
i) goes through the elements from0ton-4:O(n) - The inner loop (index
j) goes through the elements fromi+1ton-3:O(n)
- The outer loop (index
- Inside the inner loop, there is a while loop (with pointers
kandl) that could iterate up tontimes in the worst case:O(n)
Multiplying these nested iterations gives us the overall time complexity:
- Sorting:
O(n log n) - Three nested loops:
O(n^3)
Since O(n^3) dominates O(n log n), the final time complexity is O(n^3).
Space Complexity
The space complexity of the algorithm is O(m), where m is the number of unique quadruplets that sum up to the target. The space is used to store the ans list which contains the results. In the worst case, where no two quadruplets are the same, the space complexity can be as large as O(n^3) if every combination is a unique quadruplet adding up to the target. However, in average cases, m will be much smaller than n^3.
Other than that, the algorithm only uses a constant amount of extra space for pointers and variables, which does not depend on the input size and is thus O(1).
Overall, the space complexity is the larger of O(m) and O(1), which is O(m).