4Sum - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Find all unique quadruplets in an array that sum to a given target.
Sort the array to facilitate two-pointer traversal and handle duplicates.
Initialize an empty list to store the quadruplets.
Iterate through index i from 0 to n-4.
Skip duplicate values at i to avoid redundant quadruplets.
For each i, iterate through index j from i+1 to n-3.
Skip duplicate values at j to avoid redundant quadruplets.
Use two pointers, lo (j+1) and hi (n-1), to find pairs that sum with nums[i] and nums[j] to the target.
Compute the sum as nums[i] + nums[j] + nums[lo] + nums[hi].
If the sum equals the target, add the quadruplet to the answer list, increment lo, decrement hi, and skip duplicates for lo and hi.
If the sum is less than target, increment lo; otherwise, decrement hi.
Return the list of quadruplets.

Code Solution

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        answer = []
        nums.sort()

        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue

            for j in range(i+1, n):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue

                lo, hi = j + 1, n - 1
                while lo < hi:
                    summ = nums[i] + nums[j] + nums[lo] + nums[hi]
                    if summ == target:
                        answer.append([nums[i], nums[j], nums[lo], nums[hi]])
                        lo += 1
                        hi -= 1
                        while lo < hi and nums[lo] == nums[lo - 1]:
                            lo += 1
                        while lo < hi and nums[hi] == nums[hi + 1]:
                            hi -= 1
                    elif summ < target:
                        lo += 1
                    else:
                        hi -= 1

        return answer
	# Time: O(n^3)
	# Space: O(n)

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> answer;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int lo = j + 1, hi = n - 1;
                while (lo < hi) {
                    long long sum = (long long)nums[i] + nums[j] + nums[lo] + nums[hi];
                    if (sum == target) {
                        answer.push_back({nums[i], nums[j], nums[lo], nums[hi]});
                        lo++;
                        hi--;
                        while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                        while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                    } else if (sum < target) {
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
        }
        return answer;
    }
};

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> answer = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < n; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int lo = j + 1, hi = n - 1;
                while (lo < hi) {
                    long sum = (long) nums[i] + nums[j] + nums[lo] + nums[hi];
                    if (sum == target) {
                        answer.add(Arrays.asList(nums[i], nums[j], nums[lo], nums[hi]));
                        lo++;
                        hi--;
                        while (lo < hi && nums[lo] == nums[lo - 1]) lo++;
                        while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
                    } else if (sum < target) {
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
        }
        return answer;
    }
}

var fourSum = function(nums, target) {
    let answer = [];
    nums.sort((a, b) => a - b);
    let n = nums.length;

    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        for (let j = i + 1; j < n; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;

            let lo = j + 1, hi = n - 1;
            while (lo < hi) {
                let sum = nums[i] + nums[j] + nums[lo] + nums[hi];
                if (sum === target) {
                    answer.push([nums[i], nums[j], nums[lo], nums[hi]]);
                    lo++;
                    hi--;
                    while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
                    while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
                } else if (sum < target) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
    }
    return answer;
};

Detailed Explanation

Understanding the 4Sum Problem

The 4Sum problem challenges you to find all unique quadruplets in an array that sum to a specific target. Unlike the simpler 2Sum and 3Sum problems, this version requires considering four elements, making efficiency and duplicate handling critical. The key is to reduce the time complexity from O(n⁴) using nested loops to a more optimal combination of sorting and two-pointer strategies.

Efficient Strategy with Sorting and Two Pointers

To solve the 4Sum problem effectively, begin by sorting the input array. Sorting enables us to identify and skip duplicate combinations easily, which is crucial for generating unique quadruplets. After sorting, we fix two numbers using two nested loops, and for each such pair, we use the two-pointer approach to find the remaining two numbers that complete the quadruplet.

Specifically, we fix the first index i and the second index j. Then, we initialize two pointers: lo to j + 1 and hi to the end of the array. We compute the current sum of the four selected elements. If it matches the target, we add the combination to the result and skip over duplicates. If the sum is less than the target, we move the lo pointer forward. If it's greater, we move the hi pointer backward.

To avoid repeating the same quadruplets, we skip over duplicate values for i, j, lo, and hi. This ensures the result only includes unique combinations, as required by the problem.

Time and Space Complexity

Time Complexity: O(n³), where n is the number of elements in the input array. Although we use four indices, the two-pointer technique reduces one loop, making it significantly more efficient than O(n⁴).
Space Complexity: O(1) additional space, assuming the result list is not counted; otherwise, it grows with the number of valid quadruplets.

Why This Method Works

This strategy works because sorting brings structure to the problem, allowing the use of the two-pointer method, which is highly efficient in reducing unnecessary computations. It also simplifies the logic for skipping duplicates. The overall flow is systematic, making it both efficient and easy to implement once understood.

Conclusion

Mastering the 4Sum problem reinforces essential algorithmic techniques such as nested iteration control, two-pointer traversal, and duplicate handling. These strategies are crucial for solving high-complexity problems in interviews and real-world applications involving search and combination generation in sorted arrays.

Get Personalized Support at AlgoMap Bootcamp 💡