C# - two solutions - O(n^2 logn) and O(n^2)


  • 0

    Here are 2 solutions both rely on sorted array.

    1. for each element, do 2 pointer search for a two sum completing the result, skip dupes.
    2. for each element, do another for each higher index element and do a binary search through the remaining elements for the 3rd element to complete the result.

    The two pointer approach is O(n^2) and did indeed preform better from OJ timer.

        public IList<IList<int>> ThreeSum(int[] nums) 
        {
            return ThreeSum_TwoPointer(nums);
            // return ThreeSum_BinarySearch(nums);
        }
        
        public IList<IList<int>> ThreeSum_TwoPointer(int[] nums) 
        {
            Array.Sort(nums);
            IList<IList<int>> lists = new List<IList<int>>();
            
            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])
                    {
                        lists.Add(new List<int>() { nums[i], nums[left], nums[right] });
                        
                        // skip dupes
                        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--;
                    }
                }
                    
                // skip dupes
                while (i < nums.Length - 1 && nums[i] == nums[i+1]) i++;
            }
            
            return lists;
        }
        
        public IList<IList<int>> ThreeSum_BinarySearch(int[] nums) 
        {
            Array.Sort(nums);
            IList<IList<int>> lists = new List<IList<int>>();
            
            for (int i = 0; i < nums.Length - 2; i++)
            {
                for (int j = i + 1; j < nums.Length - 1; j++)
                {
                    int left = j + 1;
                    int right = nums.Length - 1;
                    while (left <= right)
                    {
                        int mid = (left + right)/2;
                        if (nums[mid] == 0 - nums[i] - nums[j])
                        {
                            lists.Add(new List<int>() { nums[i], nums[j], nums[mid] });
                            break;
                        }
                        else if (nums[mid] < 0 - nums[i] - nums[j])
                        {
                            left = mid + 1;
                        }
                        else
                        {
                            right = mid - 1;
                        }
                    }
                    
                    // skip dupes
                    while (j < nums.Length - 1 && nums[j] == nums[j+1]) j++;
                }
                    
                // skip dupes
                while (i < nums.Length - 1 && nums[i] == nums[i+1]) i++;
            }
            
            return lists;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.