3Sum

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

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

C# Program

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        
        var list = new List<IList<int>>();
        
        Array.Sort(nums);
        
        //nums = [-4,-1,-1,0,1,2]
        for(int i=0;i<nums.Length-2;i++)
        {
            int left = i + 1;
            int right = nums.Length-1;
            
            while(left < right)
            {
                if(nums[i] == 0 - nums[left] - nums[right])
                {
                    list.Add(new List<int>(){nums[i],nums[left],nums[right]});
                    
                    //Skip Duplicates
                    while(left < right && nums[left] == nums[left+1])
                        left++;
                    
                    while(left < right && nums[right] == nums[right-1])
                        right--;
                    
                    left++;
                    right--;
                }
                else if(nums[i] < 0 - nums[left] - nums[right])
                    left++;
                else
                    right--;
            }
            while(i < nums.Length-2 && nums[i] == nums[i+1])
                i++;
        }
        return list;
        
    }
}

Time Complexity: O(n * n)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s