grid47 Exploring patterns and algorithms
Nov 5, 2024
6 min read
Solution to LeetCode 18: 4Sum Problem
You are given an array of integers nums and a target value. Your task is to find all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that the sum of the four numbers equals the target value. The indices a, b, c, and d should be distinct.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `nums` of size `n`, and an integer `target` representing the target sum.
• Explanation: The only unique quadruplet that sums to 8 is [2, 2, 2, 2].
Approach: To solve this problem, we can use sorting and the two-pointer technique to efficiently find unique quadruplets that sum to the target.
Observations:
• The two-pointer technique helps to find pairs of numbers efficiently once two elements are fixed.
• Sorting the array allows us to avoid duplicates by skipping repeated elements.
• By sorting the array and using two nested loops to fix the first two numbers, we can use two pointers to find the other two numbers that sum up to the remaining target.
Steps:
• 1. Sort the input array.
• 2. Iterate through the array with two nested loops to fix the first two elements of the quadruplet.
• 3. For each pair of fixed elements, use two pointers (low and high) to find the other two elements that sum to the remaining target.
• 4. Add each valid quadruplet to a set to ensure uniqueness.
• 5. Return the set as a list of quadruplets.
Empty Inputs:
• If the array has fewer than 4 elements, it's impossible to form a quadruplet, so the result should be an empty list.
Large Inputs:
• If the array has many elements, the solution should be optimized to handle large input sizes efficiently.
Special Values:
• If all elements in the array are the same, only one unique quadruplet should be returned.
Constraints:
• Ensure that the solution works within the time and space complexity limits, especially when handling larger inputs.
vector<vector<int>> fourSum(vector<int>& nums, int target) {
Declare the `fourSum` function, which takes a vector of integers `nums` and a target integer `target` as input and returns a vector of vectors representing the unique quadruplets.
2 : Variable Initialization
int n = nums.size();
Store the size of the `nums` vector in `n` for efficient indexing.
3 : Sorting Operations
sort(nums.begin(), nums.end());
Sort the `nums` vector in ascending order to facilitate the two-pointer approach.
4 : Set Initialization
set<vector<int>> set;
Initialize a set `set` to store unique quadruplets to avoid duplicates.
5 : Variable Initialization
vector<vector<int>> output;
Initialize a vector `output` to store the final result of unique quadruplets.
6 : Nested Loops
for(int i=0; i<n-3; i++){
Start the first outer loop to iterate over the first element of the quadruplet.
7 : Nested Loops
for(int j=i+1; j<n-2; j++){
Start the second outer loop to iterate over the second element of the quadruplet, ensuring `j` is greater than `i` to avoid duplicates.
If the sum is equal to `newTarget`, insert the quadruplet into the `set` to avoid duplicates and move both pointers to find other potential quadruplets.
14 : Set Iteration
for(autoit : set){
Iterate through the unique quadruplets in the `set`.
15 : Array Manipulation
output.push_back(it);
Add each unique quadruplet to the `output` vector.
16 : Return Value
return output;
Return the `output` vector containing all unique quadruplets.
Best Case: O(n^3), where `n` is the length of the array. This occurs when no early exits happen.
Average Case: O(n^3), as the solution involves three nested loops and two pointers.
Worst Case: O(n^3), since the worst case happens when the algorithm must iterate over most combinations of elements.
Description: The time complexity is cubic in the length of the array due to the three loops and the two-pointer technique.
Best Case: O(n), as the space used by the set is dependent on the number of unique quadruplets.
Worst Case: O(n), where `n` is the number of unique quadruplets. This is the space used by the set to store unique quadruplets.
Description: The space complexity depends on the number of unique quadruplets stored in the result set.
