4Sum

Problem Statement

Given an array nums and a target, return all unique quadruplets [a, b, c, d] such that a + b + c + d == target.

Example

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

Two Pointer Approach

Sort, then fix the first two numbers with two nested loops. For the remaining two numbers, run two pointers inward. Skip duplicate values at every level to keep the quadruplets unique.

Complexity

• Time: O(n^3)
• Space: O(1) extra (ignoring output and sort)

Solution Code

Python

def fourSum(nums, target):
    nums.sort()
    n, res = len(nums), []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j-1]:
                continue
            left, right = j + 1, n - 1
            while left < right:
                s = nums[i] + nums[j] + nums[left] + nums[right]
                if s == target:
                    res.append([nums[i], nums[j], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1
                elif s < target:
                    left += 1
                else:
                    right -= 1
    return res

Java

List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    int n = nums.length;
    List<List<Integer>> res = new ArrayList<>();
    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, right = n - 1;
            while (left < right) {
                long s = (long)nums[i] + nums[j] + nums[left] + nums[right];
                if (s == target) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    left++; right--;
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                } else if (s < target) left++;
                else right--;
            }
        }
    }
    return res;
}

C++

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    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, right = n - 1;
            while (left < right) {
                long long s = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (s == target) {
                    res.push_back({nums[i], nums[j], nums[left], nums[right]});
                    left++; right--;
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                } else if (s < target) left++;
                else right--;
            }
        }
    }
    return res;
}

Key Takeaways

• Generalises the 3Sum pattern with one more fixed index.
• Duplicate skipping at each level is essential for unique results.
• The two pointer core keeps the inner search linear.