LeetCode Solution

18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Solution 1:(K-sum)

The above question is a typical k-sum problem. The loops iterates through all the possible different combinations of the array .The while loop changes the last 2 numbers of the 4 numbers needed and uses them to find the target sum.

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
 
        if(nums==null|| nums.length<4)
          return result;
 
        Arrays.sort(nums);
 
      for(int i=0; i<nums.length-3; i++){
        if(i!=0 && nums[i]==nums[i-1])
                continue;
        for(int j=i+1; j<nums.length-2; j++){
                if(j!=i+1 && nums[j]==nums[j-1])
                    continue;
                int k=j+1;
                int l=nums.length-1;
                while(k<l){
                    if(nums[i]+nums[j]+nums[k]+nums[l]<target){
                        k++;
                    }else if(nums[i]+nums[j]+nums[k]+nums[l]>target){
                        l--;
                    }else{
                        List<Integer> t = new ArrayList<Integer>();
                        t.add(nums[i]);
                        t.add(nums[j]);
                        t.add(nums[k]);
                        t.add(nums[l]);
                        result.add(t);
 
                        k++;
                        l--;
 
                        while(k<l &&nums[l]==nums[l+1] ){
                            l--;
                        }
 
                        while(k<l &&nums[k]==nums[k-1]){
                         k++;
                        }
                    }
                }
            }
        }
        return result;
    }
}

The time complexity of the above solution will be : O(n^k−1)

Solution 2:(2 pointers)

Here, we use 2 pointers to traverse through the elements of an array.The variable ‘lo’ which points to the starting of the array and the pointer ‘hi’ which is pointing to the end of the array.

public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    return kSum(nums, target, 0, 4);
    }
public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
    List<List<Integer>> res = new ArrayList<>();
    if (start == nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
        return res;
    for (int i = start; i < nums.length; ++i)
        if (i == start || nums[i - 1] != nums[i])
            for (var set : kSum(nums, target - nums[i], i + 1, k - 1)) {
                res.add(new ArrayList<>(Arrays.asList(nums[i])));
                res.get(res.size() - 1).addAll(set);
            }
    return res;
}
public List<List<Integer>> twoSum(int[] nums, int target, int start) {
    List<List<Integer>> res = new ArrayList<>();
    int lo = start, hi = nums.length - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        if (sum < target || (lo > start && nums[lo] == nums[lo - 1]))
            ++lo;
        else if (sum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1]))
            --hi;
        else
            res.add(Arrays.asList(nums[lo++], nums[hi--]));
    }
    return res;
}

The time complexity of the above solution will be : O(n^k−1)

Related Post:

LeetCode Solution