18. 4Sum

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, and d are 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(n^3)$ , 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(\log n)$ , 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.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation of the solution employs the following algorithms, data structures, and patterns:

Sorting: The nums array 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 k and l) 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 ans list.
- 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.
Maintaining Uniqueness: After adding the found quadruplet to the ans list, the third and fourth pointers are moved while skipping over any duplicates to maintain uniqueness in the ans list.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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 nums array which becomes [-2, -1, 0, 1, 2].
Initialization: We initialize an empty list ans to 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 index i up to index 3, to avoid overlap and ensure four unique indices.
Skipping Duplicates: If we encounter any element at index i or j that 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 i and j, we set pointers k = j + 1 and l = len(nums) - 1. In our example, suppose i = 0 and j = 1, then k will start at 2 and l will start at 4.
Creating the Quadruplets:
- We use a while loop to iterate with pointers k and l. For our example, with k = 2 and l = 4, we check if nums[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 k to the right (since the array is sorted, the next number will be larger).
- On the next iteration, k = 3 and l = 4. The sum (-2) + (-1) + 1 + 2 = 0 which matches the target. We add the quadruplet [-2, -1, 1, 2] to our ans list.
Maintaining Uniqueness: Next, we move both k and l to 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

1from typing import List
2
3class Solution:
4    def four_sum(self, nums: List[int], target: int) -> List[List[int]]:
5        nums_length = len(nums)  # Get the length of the nums list
6        result = []  # This will store the final quadruplets
7      
8        # If there are less than 4 numbers, no quadruplet can be formed
9        if nums_length < 4:
10            return result
11      
12        # Sort the list to make it easier to avoid duplicate quadruplets
13        nums.sort()
14      
15        # Traverse through each number, considering it as the first number of the quadruplet
16        for i in range(nums_length - 3):
17            # Skip duplicate values to prevent duplicate quadruplets
18            if i > 0 and nums[i] == nums[i - 1]:
19                continue
20          
21            # For the current first number, try to find the remaining three numbers
22            for j in range(i + 1, nums_length - 2):
23                # Skip duplicate values to prevent duplicate quadruplets
24                if j > i + 1 and nums[j] == nums[j - 1]:
25                    continue
26              
27                # Initialize two pointers, one just after j and another at the end of the list
28                left, right = j + 1, nums_length - 1
29              
30                # Try to find pairs which with i and j add up to target
31                while left < right:
32                    total = nums[i] + nums[j] + nums[left] + nums[right]
33                    if total < target:
34                        # If the sum is too small, move the left pointer to the right
35                        left += 1
36                    elif total > target:
37                        # If the sum is too large, move the right pointer to the left
38                        right -= 1
39                    else:
40                        # A quadruplet has been found
41                        result.append([nums[i], nums[j], nums[left], nums[right]])
42                        # Move both pointers and skip duplicate values
43                        left += 1
44                        right -= 1
45                        while left < right and nums[left] == nums[left - 1]:
46                            left += 1
47                        while left < right and nums[right] == nums[right + 1]:
48                            right -= 1
49      
50        return result  # Return the final list of all unique quadruplets
51

1import java.util.Arrays;
2import java.util.List;
3import java.util.ArrayList;
4
5public class Solution {
6  
7    /*
8     * Finds all unique quadruplets in the array which gives the sum of the target.
9     *
10     * @param nums The input array of integers.
11     * @param target The target sum for the quadruplets.
12     * @return A list of all unique quadruplets in the array that sum up to the target.
13     */
14    public List<List<Integer>> fourSum(int[] nums, int target) {
15        // Number of elements in the input array
16        int arraySize = nums.length;
17        // Container to store the resulting quadruplets
18        List<List<Integer>> quadrupletsList = new ArrayList<>();
19      
20        // If there are fewer than 4 elements, no quadruplet can be formed
21        if (arraySize < 4) {
22            return quadrupletsList;
23        }
24      
25        // Sort the input array to enable the two-pointer approach
26        Arrays.sort(nums);
27      
28        // Iterate over the array with the first pointer
29        for (int i = 0; i < arraySize - 3; ++i) {
30            // Skip duplicate values to ensure uniqueness of the quadruplets
31            if (i > 0 && nums[i] == nums[i - 1]) {
32                continue;
33            }
34          
35            // Iterate over the array with the second pointer
36            for (int j = i + 1; j < arraySize - 2; ++j) {
37                // Skip duplicate values to ensure uniqueness of the quadruplets
38                if (j > i + 1 && nums[j] == nums[j - 1]) {
39                    continue;
40                }
41              
42                // Initialize two pointers, one at the element after the second pointer
43                // and another at the end of the array
44                int leftPointer = j + 1, rightPointer = arraySize - 1;
45              
46                // Use a while loop to find all pairs between the left and right pointers
47                while (leftPointer < rightPointer) {
48                    // Calculate the current sum of the quadruplet
49                    long currentSum = (long) nums[i] + nums[j] + nums[leftPointer] + nums[rightPointer];
50                  
51                    // If the sum is less than target, move the left pointer to the right to increase the sum
52                    if (currentSum < target) {
53                        ++leftPointer;
54                    } 
55                    // If the sum is greater than target, move the right pointer to the left to decrease the sum
56                    else if (currentSum > target) {
57                        --rightPointer;
58                    } 
59                    // If the sum is equal to the target, a quadruplet is found
60                    else {
61                        quadrupletsList.add(Arrays.asList(nums[i], nums[j], nums[leftPointer], nums[rightPointer]));
62                        // Move the left pointer to the right and the right pointer to the left
63                        leftPointer++;
64                        rightPointer--;
65                        // Skip over any duplicate values for the third and fourth numbers in the quadruplet
66                        while (leftPointer < rightPointer && nums[leftPointer] == nums[leftPointer - 1]) {
67                            leftPointer++;
68                        }
69                        while (leftPointer < rightPointer && nums[rightPointer] == nums[rightPointer + 1]) {
70                            rightPointer--;
71                        }
72                    }
73                }
74            }
75        }
76        return quadrupletsList;
77    }
78}
79

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find all unique quadruplets in the array which gives the sum of target.
7    std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
8        // Get the number of elements in the array.
9        int n = nums.size();
10        // Initialize the vector to store the quadruplets.
11        std::vector<std::vector<int>> quadruplets;
12      
13        // If there are fewer than 4 elements, no quadruplet can be formed, return empty list.
14        if (n < 4) {
15            return quadruplets;
16        }
17      
18        // Sort the array to handle duplicates and make two-pointer approach feasible.
19        std::sort(nums.begin(), nums.end());
20      
21        // Iterate over the array with the first pointer.
22        for (int i = 0; i < n - 3; ++i) {
23            // Skip duplicates for the first number.
24            if (i > 0 && nums[i] == nums[i - 1]) {
25                continue;
26            }
27          
28            // Iterate with the second pointer, starting from the next element after i.
29            for (int j = i + 1; j < n - 2; ++j) {
30                // Skip duplicates for the second number.
31                if (j > i + 1 && nums[j] == nums[j - 1]) {
32                    continue;
33                }
34              
35                // Initiate two pointers, one from the next element after j and the other from the end of the array.
36                int left = j + 1;
37                int right = n - 1;
38              
39                // While the left pointer is to the left of the right pointer.
40                while (left < right) {
41                    // Calculate the sum of the values at the four pointers.
42                    long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];
43                  
44                    // If the sum is less than the target, move the left pointer to the right.
45                    if (sum < target) {
46                        ++left;
47                    }
48                    // If the sum is greater than the target, move the right pointer to the left.
49                    else if (sum > target) {
50                        --right;
51                    }
52                    // If the sum of four numbers is equal to the target, we found a quadruplet.
53                    else {
54                        // Add the quadruplet to the list of results.
55                        quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});
56                        // Move both pointers to get ready for the next potential quadruplet.
57                        ++left;
58                        --right;
59                      
60                        // Skip duplicates for the third number.
61                        while (left < right && nums[left] == nums[left - 1]) {
62                            ++left;
63                        }
64                      
65                        // Skip duplicates for the fourth number.
66                        while (left < right && nums[right] == nums[right + 1]) {
67                            --right;
68                        }
69                    }
70                }
71            }
72        }
73        // Return all the unique quadruplets found.
74        return quadruplets;
75    }
76};
77

1// This function finds all unique quadruplets that sum up to the given target.
2function fourSum(nums: number[], target: number): number[][] {
3    const lengthOfNums = nums.length; // Length of the input array
4    const quadruplets: number[][] = []; // Array to store the resulting quadruplets
5  
6    // If the array has fewer than 4 numbers, we can't find any quadruplets.
7    if (lengthOfNums < 4) {
8        return quadruplets;
9    }
10
11    // Sort the numbers to easily avoid duplicates and use two-pointer method
12    nums.sort((a, b) => a - b);
13
14    // Iterate over the array with the first pointer
15    for (let first = 0; first < lengthOfNums - 3; ++first) {
16        // Skip duplicate values to avoid redundant quadruplets
17        if (first > 0 && nums[first] === nums[first - 1]) {
18            continue;
19        }
20
21        // Iterate with the second pointer, which starts just after the first pointer
22        for (let second = first + 1; second < lengthOfNums - 2; ++second) {
23            // Skip duplicate values for the second pointer
24            if (second > first + 1 && nums[second] === nums[second - 1]) {
25                continue;
26            }
27
28            let third = second + 1; // Initialize the third pointer
29            let fourth = lengthOfNums - 1; // Initialize the fourth pointer
30
31            // Use two pointers (third and fourth) to find the target sum
32            while (third < fourth) {
33                const currentSum = nums[first] + nums[second] + nums[third] + nums[fourth];
34              
35                // If the current sum is less than the target, we need to increase it
36                if (currentSum < target) {
37                    ++third;
38                }
39                // If the current sum is greater than the target, we need to reduce it
40                else if (currentSum > target) {
41                    --fourth;
42                } 
43                // If we found a quadruplet that sums up to the target
44                else {
45                    quadruplets.push([nums[first], nums[second], nums[third], nums[fourth]]);
46                    ++third;
47                    --fourth;
48                  
49                    // Skip over any duplicate values for the third pointer
50                    while (third < fourth && nums[third] === nums[third - 1]) {
51                        ++third;
52                    }
53                  
54                    // Skip over any duplicate values for the fourth pointer
55                    while (third < fourth && nums[fourth] === nums[fourth + 1]) {
56                        --fourth;
57                    }
58                }
59            }
60        }
61    }
62  
63    return quadruplets; // Return the array of quadruplets
64}
65

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 from 0 to n-4: O(n)
- The inner loop (index j) goes through the elements from i+1 to n-3: O(n)
Inside the inner loop, there is a while loop (with pointers k and l) that could iterate up to n times 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).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know