Four Sum

Problem Statement 

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

0 <= a, b, c, d < n
a, b, c, and d are distinct.
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]]

Constraints:
● 1 <= nums.length <= 200
● -109 <= nums[i] <= 109
● -109 <= target <= 109

Step 1 : – Template Implemenation.

There are two types of two pointer templates.

1). Opposite direction two pointer template

2). Same direction two pointer template

Based on our analysis of the Four Sum problem statement, this is a target-based problem where we need to find all unique quadruplets whose sum equals zero (the target). Therefore, we should use the opposite direction pointers template as our foundation. we need to extend the opposite direction pointers template from two pointers to four pointers. To achieve this, we introduce two additional for loop to handle the extra index. Inside this loop, we set the i pointer at the first index and j pointer of second loop at the second index of the array and move the left pointer two step ahead in the array to begin the four-pointer process and as per the approach sort the array with Arrays sort() method.

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

        for (int i = 0; i < nums.length - 3; i++) {
            
            for (int j = i + 1; j < nums.length - 2; j++) {
                
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                //code
                    if (param1 == target) {
                        //code
                        left++;
                        right--;
                    } else if (param1 < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

Step 2 : – I/O parameters.        

Template input parameters :- To calculate the value of  param1, we add the values of the elements at the i, j, left and right indices. This sum becomes our quadruplets and replaced param2 with the target value as 0.

Output parameter :- We need to return the quadruplet formed by the elements at indices i, j, left, and right when their combined sum equals zero.

 

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

        for (int i = 0; i < nums.length - 3; i++) {
            
            for (int j = i + 1; j < nums.length - 2; j++) {
                
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long total = (long) nums[i] + nums[j] + nums[left] + nums[right]; // avoid overflow

                    if (total == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        
                        left++;
                        right--;
                    } else if (total < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

Step 3: – Skip the duplicates.
We need to skip duplicates for the i, j index in the four-pointer approach to ensure unique quadruplets in the result.

 

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

        for (int i = 0; i < nums.length - 3; i++) {
            // Skip duplicates for i
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.length - 2; j++) {
                // Skip duplicates for j
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long total = (long) nums[i] + nums[j] + nums[left] + nums[right]; // avoid overflow

                    if (total == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        
                        left++;
                        right--;
                    } else if (total < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

Step 4 : – Handle duplicate values for the left and right pointers
The corner test case [-2,-1,-1,1,1,2,2] fails because it produces duplicate triplets in the result.
To resolve this, we need to skip over duplicate values for both the left and right pointers after finding a valid triplet.
This ensures that each unique quadruplets is included only once in the final result.

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

        for (int i = 0; i < nums.length - 3; i++) {
            
            for (int j = i + 1; j < nums.length - 2; j++) {
                
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long total = (long) nums[i] + nums[j] + nums[left] + nums[right]; // avoid overflow

                    if (total == target) {
                        result.add(Arrays.asList(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 (total < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

Final Code : – 

 

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

        for (int i = 0; i < nums.length - 3; i++) {
            // Skip duplicates for i
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            for (int j = i + 1; j < nums.length - 2; j++) {
                // Skip duplicates for j
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long total = (long) nums[i] + nums[j] + nums[left] + nums[right]; // avoid overflow

                    if (total == target) {
                        result.add(Arrays.asList(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 (total < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
}
Prev
Next
Scroll to Top