Blogs Hub

by Sumit Chourasia | Oct 24, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

4Sum - Array - Medium - LeetCode

4Sum - Array - Medium - LeetCode

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.

Notice that the solution set must not contain duplicate quadruplets.

 

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 = [], target = 0
Output: []
 

Constraints:

0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        var res = new List<IList<int>>();
        var set = new HashSet<string>();
        for(int i=0;i<nums.Length-3;i++){
            for(int j=i+1;j<nums.Length-2;j++){
                for(int k=j+1, l=nums.Length-1;k<l;){
                    int sum = nums[i]+nums[j]+nums[k]+nums[l];
                    if(sum == target){
                        if(!set.Contains(GetKey(nums[i],nums[j],nums[k],nums[l]))){
                            set.Add(GetKey(nums[i],nums[j],nums[k],nums[l]));
                            res.Add(BuildList(nums[i],nums[j],nums[k],nums[l]));
                        }
                        k++;
                    }
                    else if(sum>target){
                        l--;
                    }
                    else if(sum<target){
                        k++;
                    }
                }
            }
        }
        
        return res;
    }
    
    private string GetKey(int a, int b, int c, int d){
        return a.ToString()+":"+b.ToString()+":"+c.ToString()+":"+d.ToString();
    }
    
    private List<int> BuildList(int a, int b, int c, int d){
        var res = new List<int>();
        res.Add(a);
        res.Add(b);
        res.Add(c);
        res.Add(d);
        return res;
    }
}

Time Complexity: O(n^3)

Space Complexity: O(n)