Leetcode 18: 4 sum | Editorial solution study

Here is the link.

 C# | k sum problem | Time complexity: O(N^(k-1)) | Editorial | July 2023

jianminchen

774

0

19 minutes ago

C#

Intuition

It is a good idea to write a solution based on editorial solution, which is written for Leetcode premium account. The idea is to solve a k sum problem using time complexity O(N^(k - 1)).

Approach

C# solution highlights:

1. Sort the array
2. Base case: Two sum problem using two pointer technique, O(N) time complexity
3. Keep unique quadruplet - remove duplicate
4. C# List APIs: AddRange, Insert(index, int)
5. 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; 
        }
    }
}