C# - O(n^3) - sorted 2 Sum + 2 pointer - key is dupe skip


  • 0

    do an O(n^2) 2 sum iteration and at each iteration search the remaining array with left and right pointer to find 2 more elements that make up the remaining target. The key is that each time you need to skip over elements that will produce dupes. And because the array has been sorted you can just check if it matches it's previous value to achieve this.

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