LeetCode 18 Solution - 4Sum

Problem Statement (LeetCode 18)

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

• a, b, c, and d are distinct indices.
• 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]]

---

Optimal Approach: Sorting + Two Pointers

Intuition

This problem is a generalization of the "3Sum" problem, which can be solved using a sorting technique combined with two-pointer approach.

1. Sorting the Array: Sorting the input array helps in efficiently skipping duplicate values and ensures that the two-pointer technique works effectively.
2. Using Two Pointers: After fixing the first two numbers using two pointers, the problem reduces to a "two-sum" problem, which can be solved in linear time.

Why Sorting + Two Pointers Works

• Sorting the array allows us to skip duplicates effectively.
• By fixing two numbers at the start and end of the remaining array, we can move the pointers inward to find the target sum.
• This reduces the time complexity significantly by avoiding the brute force approach of checking all quadruples.

---

LeetCode-Compatible C++ Code

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if (nums.size() < 4) return result;  // Early return if not enough numbers
        
        // Sorting the array to handle duplicates and use two pointers
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size() - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;  // Skip duplicates for i
            for (int j = i + 1; j < nums.size() - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;  // Skip duplicates for j
                
                int left = j + 1, right = nums.size() - 1;
                
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    
                    if (sum == target) {
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        // Skip duplicates for left and 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;  // Need a larger sum
                    } else {
                        --right;  // Need a smaller sum
                    }
                }
            }
        }
        
        return result;
    }
};

---

Step-by-Step Explanation of Code

1. Input Check:
   We start by checking if the size of nums is less than 4, in which case no quadruplet can be formed. If this is true, we return an empty result.

2. Sorting the Array:
   We sort the array nums. This helps us efficiently skip duplicates and simplifies the process of using two pointers.

3. First Loop (i):
   We iterate over the array with index i. For each i, we check if it's the same as the previous element to avoid duplicate results. If so, we skip it.

4. Second Loop (j):
   Inside the first loop, we iterate with index j starting from i+1. Again, we skip duplicate values to avoid generating duplicate quadruplets.

5. Two Pointers (left, right):
   After selecting i and j, we use two pointers: left starts from j+1 and right starts from the end of the array. We calculate the sum of nums[i], nums[j], nums[left], and nums[right].

   • If the sum matches the target, we add the quadruplet to result.
   • We then skip duplicates for left and right pointers to ensure each quadruplet is unique.
   • If the sum is less than the target, we move the left pointer to the right to increase the sum.
   • If the sum is greater than the target, we move the right pointer to the left to decrease the sum.

6. Return Result:
   After all loops finish, we return the result which contains all unique quadruplets.

---

Dry Run with Example

Input: nums = [1, 0, -1, 0, -2, 2], target = 0

1. Sorted Input: [-2, -1, 0, 0, 1, 2]
2. i = 0:
   • j = 1: [-2, -1]
     • left = 2, right = 5: Sum = -2 + (-1) + 0 + 2 = -1 (less than 0)
     • Move left pointer to 3.
     • left = 3, right = 5: Sum = -2 + (-1) + 0 + 2 = -1 (less than 0)
     • Move left pointer to 4.
     • left = 4, right = 5: Sum = -2 + (-1) + 1 + 2 = 0 (found a match, add [-2, -1, 1, 2])
   • Skip duplicate values for j and proceed to next i.

Final Output: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (4 Nested Loops)	O(n^4)	O(1)	Too inefficient for large arrays (4 nested loops).
Sorting + Two Pointers (Optimal)	O(n^3)	O(1)	Efficient solution for this type of problem.
HashMap/HashSet	O(n^3)	O(n)	Possible, but extra space and complexity are not necessary here.
Dynamic Programming (DP)	O(n^4)	O(n^3)	Not applicable as no sub-problems can be re-used.

---

Why Sorting + Two Pointers is the Best

• Time Complexity: O(n^3), because we are using two nested loops (i, j) to select the first two elements and the two-pointer technique for the remaining two elements. This is much better than brute force (O(n^4)).
• Space Complexity: O(1), since we are using only a few extra variables and storing the result.
• Optimal Solution: This approach leverages sorting and two-pointer techniques to efficiently generate all unique quadruplets.

---

Complexity Analysis

• Time Complexity: O(n^3)
  The outer two loops iterate O(n^2) times, and the two-pointer technique iterates in linear time, resulting in O(n^3).

• Space Complexity: O(1)
  We are only using constant extra space (apart from the result vector).

---

Conclusion

✅ Best Approach: Sorting + Two Pointers
✅ Time Complexity: O(n^3)
✅ Space Complexity: O(1)
✅ Optimal for Handling Large Arrays Efficiently

Recommended Problems for Practice

1. 3Sum (LeetCode 15)
2. Two Sum (LeetCode 1)
3. Sum 4 (LeetCode 18)

🚀 Master the 4Sum Problem with Sorting and Two-Pointer Techniques!