Here is the link.
C# | k sum problem | Time complexity: O(N^(k-1)) | Editorial | July 2023
774
0
19 minutes ago
Intuition
Approach
- Sort the array
- Base case: Two sum problem using two pointer technique, O(N) time complexity
- Keep unique quadruplet - remove duplicate
- C# List APIs: AddRange, Insert(index, int)
- Compare editorial Java solution, and understand difference between Java and C# related to List and APIs.
Complexity
- Time complexity:
- Space complexity:
Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _18_4sum_study
{
class Program
{
static void Main(string[] args)
{
var test = new Program();
var result = test.FourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);
// output
// [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
}
/// <summary>
/// Code study on July 17, 2023
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns></returns>
public IList<IList<int>> FourSum(int[] nums, int target)
{
Array.Sort(nums);
return kSum(nums, target, 0, 4);
}
/// <summary>
///
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <param name="start"></param>
/// <param name="k"></param>
/// <returns></returns>
private IList<IList<int>> kSum(int[] nums, long target, int start, int k)
{
var result = new List<IList<int>>();
var length = nums.Length;
if (start == length)
{
return result;
}
long averageValue = target / k;
if (averageValue < nums[start] || averageValue > nums[length - 1])
{
return result;
}
// base case
if (k == 2)
{
return twoSum(nums, target, start);
}
for (int i = start; i < length; i++)
{
// pruning - remove duplicate ones - check previous element in sorted array
if (i == start || nums[i - 1] != nums[i])
{
var current = nums[i];
var kResult = kSum(nums, target - current, i + 1, k - 1);
for (int j = 0; j < kResult.Count; j++)
{
kResult[j].Insert(0, current);
}
result.AddRange(kResult);
}
}
return result;
}
/// <summary>
/// Two sum classical algorithm
/// Remove duplicate - check previous
/// low -> compare to low - 1
/// high -> compare to high + 1
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <param name="start"></param>
/// <returns></returns>
private IList<IList<int>> twoSum(int[] nums, long target, int start)
{
var result = new List<IList<int>>();
int low = start;
var length = nums.Length;
int high = length - 1;
while (low < high)
{
int sum = nums[low] + nums[high];
if (sum < target || (low > start && nums[low] == nums[low - 1]))
{
low++;
}
else if(sum > target || (high < length - 1 && nums[high] == nums[high + 1]))
{
high--;
}
else
{
result.Add((new int[]{nums[low], nums[high]}).ToList());
low++;
high--;
}
}
return result;
}
}
}