Leetcode discuss: 18. 4Sum

 March 17, 2022

Here is the link.

C# | Sorting, sliding window, skip duplicate | Time: O(N^3)

March 17, 2022
Introduction
I did review last five year my few practice, and I chose to study one discuss post without using HashSet, extra space to remove duplicate entries.

C# code | sliding window | Skip duplicate
I did review the discuss post and chose to study and write my own code.

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _4_sum
{
    class Program
    {
        static void Main(string[] args)
        {
            /*
            Input: nums = [1,0,-1,0,-2,2], target = 0
            Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
            */
            var result = FourSum(new int[] { 1, 0, -1, 0, -2, 2 }, 0);
            var s = string.Join(",", result[0]);
            Debug.Assert(s.CompareTo("-2,-1,1,2") == 0 ||
                s.CompareTo("-2,0,0,2") == 0 ||
                s.CompareTo("-1,0,0,1") == 0);
        }

        /// <summary>
        /// code study on March 17, 2022
        /// https://leetcode.com/problems/4sum/discuss/278435/C-same-as-3SUM
        /// 
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static IList<IList<int>> FourSum(int[] nums, int target)
        {
            var length = nums.Length;

            Array.Sort(nums);

            var result = new List<IList<int>>();

            for (int i = 0; i < length; i++)
            {
                var first = nums[i];

                // first number: skip first number to remove duplicate 4 numbers
                if (i > 0 && nums[i - 1] == first)
                {
                    continue;
                }

                for (int j = i + 1; j < length; j++)
                {
                    var second = nums[j];
                    // second number: skip to remove duplicate 4 numbers if it is not the first one in the for loop
                    if (j > i + 1 && nums[j - 1] == second)
                    {
                        continue;
                    }

                    // Last two: using two pointer technique - sliding window O(N) time
                    var left  = j + 1;
                    var right = length - 1;

                    while (left < right)
                    { 
                        var sum = first + second + nums[left] + nums[right];
                        if (sum == target)
                        {
                            result.Add(new List<int>() { first, second, nums[left], nums[right] });

                            // third number: skip to remove duplicate
                            while (left < right && nums[left] == nums[left + 1])
                            {
                                left++;
                            }

                            // fourth number: skip to remove duplicate
                            while (left < right && nums[right] == nums[right - 1])
                            {
                                right--;
                            }

                            left++;
                            right--;
                        }
                        else if (sum < target)
                        {
                            left++;
                        }
                        else
                        {
                            right--;
                        }
                    }
                }
            }

            return result;
        }
    }
}