Leetcode 18 - 4 sum - pass all test cases

Leetcode18_4sum.cs

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

namespace _4sum
{
    /// Leetcode 18 
    /// https://leetcode.com/problems/4sum/#/description
    /// 
    /// S = 20, look for 4 of them 
    /// 2 of them, it is simple, 2 sum -> 20, 
    /// 2, check if there is 18 , one 2 + 18 
    /// 4 sum -> brute force -> O(n* (n-1) * (n-2)*(n-3))
    /// all possible 2 sum -> hashtable 
    /// O(n), n * (n-1)   option -> Sum, value  
    /// sort array 
    /// sum, i, j
    /// go over each two sum, 20 - sum, and see if dictionary, 
    /// Dictionary< int, int[]>
    /// 0 1 2 3 4 5 7 9 
    /// two sum -> O(n^3)
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase2(); 
        }

        public static void RunTestcase()
        {
            var result = FourSum(new int[] { -2, -1, 0, 0, 1, 2 }, 0);
        }

        public static void RunTestcase2()
        {
            var result = FourSum(new int[] { -3, -2, -1, 0, 0, 1, 2, 3 }, 0);
        }

        /// O(n^3)
        /// 
        //public IList<IList<int>> FourSum(int[] nums, int target)
        static IList<IList<int>> FourSum(int[] numbers, int target) 
        {
            IList<IList<int>> result = new List<IList<int>>();

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

            int length = numbers.Length; 
            for(int i = 0; i < length - 3; i++)
            {
                for(int j = i + 1; j < length - 2; j++)
                {
                    var number1 = numbers[i];
                    var number2 = numbers[j]; 
                    var twoSum = number1 + number2; 
                
                    var search = target - twoSum; 
          
                    // two pointer linear scan the array to find if there are two sum
                    var found = linearScanTwoSum(numbers, j + 1, search);
                    if(found.Count != 0)
                    {                        
                        foreach (var item in found)
                        {
                            IList<int> fourNumbers = new List<int>();

                            fourNumbers.Add(number1);
                            fourNumbers.Add(number2);
                            fourNumbers.Add(item[0]);
                            fourNumbers.Add(item[1]);

                            result.Add(fourNumbers);
                        }
                    }
                }                   
            }

            return removeDuplicate(result); 
        }               

        private static IList<IList<int>> removeDuplicate(IList<IList<int>> numbers)
        {
            var uniqueNumbers = new List<IList<int>>();
            var set = new HashSet<string>(); 

            foreach(var item in numbers)
            {
                var key = encodeKey(item);
                if (set.Contains(key))
                {
                    continue; 
                }

                uniqueNumbers.Add(item); 
                set.Add(key); 
            }

            return uniqueNumbers; 
        }

        private static string encodeKey(IList<int> numbers)
        {
            var key = ""; 
            foreach (var item in numbers)
            {
                key += item + " ";
            }

            return key; 
        }

        /// <summary>
        /// O(n) time complexity
        /// two pointer techniques - get all possible pairs 
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="indexExcluded1"></param>
        /// <param name="indexExclude2"></param>
        /// <param name="search"></param>
        /// <returns></returns>
        private static IList<int[]> linearScanTwoSum(int[] arr, int startNo, int search)
        {
            var pairs = new List<int[]>(); 

            int length = arr.Length;
            int start = startNo;
            int end = length - 1;

            while (start < end)
            {
                var left  = arr[start];
                var right = arr[end];

                var twoSum = left + right;
                if (twoSum == search)
                {
                    pairs.Add(new int[] { left, right });

                    start++;
                    end--; 
                }
                else if (twoSum > search)
                {
                    end--;
                }
                else
                {
                    start++;
                }
            }

            return pairs;
        }
    }
}