algoadvance

Leetcode 18. 4Sum

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.

Note:

• The solution set must not contain duplicate quadruplets.

You need to implement a function in C++:

vector<vector<int>> fourSum(vector<int>& nums, int target);

Clarifying Questions:

1. Input Size Constraints: Are there any constraints on the size of the array?
   • Typically constraints can help guide how we approach the problem.
2. Element Values: Are there any constraints on the values of integers within the array?
3. Output Format: Should the quadruplets be returned in any specific order, or are they just required to be unique?
4. Duplicates: Should the solution take into account the possibility of duplicate numbers but ensure unique quadruplets?

Assuming:

• The size of the array nums is reasonably small (e.g., ≤ 200).
• The integers can be any value within the typical integer range.
• No specific output order, but results must be unique.

Strategy:

1. Sorting: Start by sorting the array to ease the identification of duplicates and manage the two-pointer approach efficiently.

2. Iterative Reduction: Use a nested loop to fix the first two numbers, and then apply the two-pointer technique to find pairs that match the remaining target for the other two numbers.

3. Avoid Duplicates: After sorting, skip over duplicate values for both sets of elements (the fixed elements and pair elements).

4. Two-pointer Technique: Within the nested loop, use the left and right pointers to find sums efficiently.

Code:

Here is the complete C++ implementation:

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    int n = nums.size();

    if (n < 4) return result;

    sort(nums.begin(), nums.end());

    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
            
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                
            int left = j + 1;
            int right = n - 1;
                
            while (left < right) {
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                    
                if (sum == target) {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                        
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
        
    return result;
}

Time Complexity:

The time complexity of this approach is:

1. Sorting: O(n log n) where n is the number of elements in the nums array.
2. Nested Loops:
   • The outer two loops run O(n^2).
   • The innermost while loop runs in linear time, i.e., O(n) in the worst case.

Overall, the time complexity is O(n^3). Although this isn’t optimal for very large arrays, it is acceptable given reasonable constraints (e.g., n ≤ 200).

Additional Notes:

• Handle cases where integer overflows might occur by using long long for sum calculations.
• Ensure to skip duplicates to maintain unique quadruplet results.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?