Leetcode: 4 sum

Here is the article. 

C# | Fail fast | What to learn? | Stay humble | July 14, 2023

jianminchen

774

5

3 hours ago

C#

Intuition

The idea is to work on a better solution than brute force, O(N^4). Sorting first, since it only takes O(nlogn) time. Next is to work on O(N^2) time complexity to construct two loops for third number and fourth number, meanwhile a hashmap is built to store all possible two sum with index position of the array.

Approach

I worked on 3+ submissions, and failed two times and then succeeded last time. One is TLE with an array with length 200, all with value 2, target is 8.

Next is "Wrong Submission", for integer 10^9, four of them as input array.

My solution is to add the following code to skip duplicate quadruplet.

 // pruning - avoid TLE
if(fourth > (third + 2 ) && numbers[fourth] == numbers[fourth - 2])
{
   continue; 
}

And declare hashmap using long instead of int in the following:

  // record first two number possible sum's hashmap 
  var map = new Dictionary<long, IList<int[]>>();

And declare long data type instead of int for variable sum:

long sum = thirdValue + fourthValue;

Complexity

• Time complexity:

Time complexity:
Three loops

 for (int third = 0; third < length - 1; third++)
 ...
    for (int fourth = third + 1; fourth < length; fourth++)
    ...
        foreach (var item in map[search])

O(N^2) * O(M), M is hashmap size - upper bound is O(N^2)

In order to reduce hashmap size, it is important to remove duplicate entry in hashmap, so that the size can be lowered for extreme case: aray size 200, all with value 2, target 8. M can be lowered from above 10,000+ to 1.

• Space complexity:

Space complexity:
O(N^2)

Code

/// <summary>
        /// Code review 
        /// July 14, 2023
        /// Time complexity: O(N^2), N is the length of array numbers
        /// Space complexity: O(N^2)
        /// </summary>
        /// <param name="numbers"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public IList<IList<int>> FourSum(int[] numbers, int target)
        {
            var quadruplets = new List<IList<int>>();

            if (numbers == null || numbers.Length == 0)
            {
                return quadruplets;
            }
            
            Array.Sort(numbers);

            // record first two number possible sum's hashmap 
            var map = new Dictionary<long, IList<int[]>>();
            var set = new HashSet<string>(); 

            // quadruplets unique - key using ,
            var keys = new HashSet<string>();

            var length = numbers.Length;

            // Work on last two numbers - third and fourth, time complexity:O(N^2)
            // all unique values - remove duplicate 
            for (int third = 0; third < length - 1; third++)
            {
                var thirdValue = numbers[third];

                for (int fourth = third + 1; fourth < length; fourth++)
                {   // pruning - avoid TLE
                    if(fourth > (third + 2 ) && numbers[fourth] == numbers[fourth - 2])
                    {
                        continue; 
                    }

                    var fourthValue = numbers[fourth];
                    long sum = thirdValue + fourthValue;

                    var search = target - sum;

                    if (!map.ContainsKey(search))
                    {
                        continue;
                    }

                    foreach (var item in map[search])
                    {
                        var first = numbers[item[0]];
                        var second = numbers[item[1]];

                        var quadruplet = new int[] { first, second, thirdValue, fourthValue };
                        var key = string.Join(",", quadruplet);

                        if (!keys.Contains(key))
                        {
                            keys.Add(key);
                            quadruplets.Add(new List<int>(quadruplet));
                        }
                    }
                }

                // It is time to add visited element into two sum dictionary.
                // Argue that no need to add any two indexes smaller than third, why? 
                // Just prove that it covers all possible numbers - easy to prove it!                
                for (int firstId = 0; firstId < third; firstId++)
                {
                    var firstNumber = numbers[firstId];
                    var firstTwoSum = firstNumber + thirdValue;

                    var newItems = new int[] { firstId, third };
                    var newKey = numbers[firstId] + "," + numbers[third];

                    // prune - reduce the size of value - List<int> length
                    if (!map.ContainsKey(firstTwoSum))
                    {
                        var items = new List<int[]>();

                        map.Add(firstTwoSum, items);
                    }

                    if (!set.Contains(newKey))
                    {
                        map[firstTwoSum].Add(newItems);
                        set.Add(newKey);
                    }
                }
            }

            return quadruplets;
        }