4sum.java

/*18. 4Sum
Solved
Medium
Topics
premium lock icon
Companies
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 */

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int i,j,k,l;
        long sum1,sum2,remaining;
        int size=nums.length;
        for(i=0;i<size-1;i++)
        {
            if(i>0&&nums[i]==nums[i-1])
            {
                continue;
            }
            for(j=i+1;j<size;j++)
            {
                if(j>i+1&&nums[j]==nums[j-1])
                {
                    continue;
                }
                sum1=nums[i]+nums[j];
                remaining=target-sum1;
                k=j+1;
                l=size-1;
                while(k<l)
                {
                    sum2=nums[k]+nums[l];
                    if(sum2<remaining)
                    {
                        k++;
                    }
                    else if(sum2>remaining)
                    {
                        l--;
                    }
                    else
                    {
                        List<Integer> temp=new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[k]);
                        temp.add(nums[l]);
                        list.add(temp);
                        k++;
                        l--;
                        while(k<l&&nums[k]==nums[k-1])k++;
                        while(k<l&&nums[l]==nums[l+1])l--;
                    }
                }
            }
            
        }
        return list;  
    }
}

//logic-- sort+2 loops+2 pointers
// tc= O(n^3)
//sc= O(k)