4 sum mocking experience - code practice - May 28, 2017

4sum_mockingexperience_codepractice.s

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

namespace _4sum
{
    /// 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)
        {
        }

        /// O(n^3)
        static int[] findArrayQuadruplet(int[] arr, int s) 
        {
            // your code goes here
            if(arr == null || arr.Length == 0) return new int[0]; 
      
            Array.Sort(arr); 
      
            int length = arr.Length; 
            for(int i = 0; i < length - 1; i++)
            {
                for(int j = i+1; j < length; j++)
                {
                    var number1 = arr[i]; 
                    var number2 = arr[j]; 
                    var twoSum = number1 + number2; 
          
                    var search = s - twoSum; 
          
                    // two pointer linear scan the array to find if there are two sum
                    var found = linearScanTwoSum(arr, i, j, search);
                    if(found.Length != 0)
                    {
                        var result = new int[4]; 
                        result = new int[]{number1, number2, arr[found[0]], arr[found[1]]}; 
                        Array.Sort(result); 
                        return result; 
                    }
                }                   
            }

            return new int[0]; 
        }

        /// <summary>
        /// O(n) time complexity
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="indexExcluded1"></param>
        /// <param name="indexExclude2"></param>
        /// <param name="search"></param>
        /// <returns></returns>
        private static int[] linearScanTwoSum(int[] arr, int indexExcluded1, int indexExclude2, int search)
        {
            int length = arr.Length;
            int start = 0;
            int end = length - 1;
            while (start < end)
            {
                // start, end 
                if (start == indexExcluded1 || start == indexExclude2)
                {
                    start++;
                    continue;
                }
                if (end == indexExcluded1 || end == indexExclude2)
                {
                    end--;
                    continue;
                }

                // assume start, end value can be checked
                var twoSum = arr[start] + arr[end];
                if (twoSum == search)
                {
                    return new int[] { start, end };
                }
                else if (twoSum > search)
                {
                    end--;
                }
                else
                {
                    start++;
                }
            }

            return new int[0];
        }
    }
}