Striver's SDE Sheet Journey - #19 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,

1. 0 <= a, b, c, d < n
2. a, b, c, and d are distinct.
3. nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example

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

Result : [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Solution 1

fix three pointers and look for the last one

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

nums = [1,0,-1,0,-2,2]
        | |  | < look for the last one >
        i j  k

step-1 sort the array nums and initialise an variable ans.

step-2 run three loops linearly for i, j, k pointers

1. find the last element, using binary search.
2. if the last element found then add the quadruplet to ans

Java

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        Set<List<Integer>> ans = new HashSet<List<Integer>>();
        int n = nums.length;

        Arrays.sort(nums);

        for(int i=0; i<n; i++){

            for(int j=i+1; j<n; j++){

                for(int k=j+1; k<n; k++){

                    int x = target - (nums[i] + nums[j] + nums[k]);

                    if(Arrays.binarySearch(Arrays.copyOfRange(nums,k+1,n),x) >= 0){
                        List<Integer> r = new ArrayList<Integer>();
                        r.add(nums[i]);
                        r.add(nums[j]);
                        r.add(nums[k]);
                        r.add(x);

                        ans.add(r);
                    }
                }
            }
        }

        List<List<Integer>> result = new ArrayList<List<Integer>>();

        for(List<Integer> list : ans){
            result.add(list);
        }

        return result;
    }
}