Here is the article.
C# | Fail fast | What to learn? | Stay humble | July 14, 2023
774
5
3 hours ago
Intuition
Approach
// pruning - avoid TLE
if(fourth > (third + 2 ) && numbers[fourth] == numbers[fourth - 2])
{
continue;
} // record first two number possible sum's hashmap
var map = new Dictionary<long, IList<int[]>>();long sum = thirdValue + fourthValue;Complexity
- Time complexity:
for (int third = 0; third < length - 1; third++)
...
for (int fourth = third + 1; fourth < length; fourth++)
...
foreach (var item in map[search])
- Space complexity:
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;
}