Blogs Hub

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

3Sum - Array - Medium - LeetCode

3Sum - Array - Medium - LeetCode

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

 

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Example 2:

Input: nums = []
Output: []
Example 3:

Input: nums = [0]
Output: []
 

Constraints:

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

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

Time Complexity: O(n^2)

Space Complexity: O(n)

Contributed By: Sumit Chourasia
Unique Paths - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Teemo Attacking - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Maximum Swap - Array - Medium - LeetCode