4 sum - practice code - written in C#, need to complete the code first, and then run against Leetcode online judge.

4sum_practicecode.cs

using System;

// [2,3,4,5,6,7] target = 22
// [4,5,6,7]
// O(n^3) 
// O(n^2)   hashtable 
// nlogn -> sort the array -> given 22, 
// give all possible two sum -> 2, 3 -> 5, search two sum -> 17
// a < b < c < d , a + b < c + d, 
// -> [2, 7, 4, 0, 9, 5, 1, 3], s = 20 
// [0, 1, 2, 3, 4, 5, 7, 9] - 8 elements, sum = 20 
// O(n^2) -> (n - 2) * (n - 1), a <= b <= c <= d, a, b-> two sum , two sum -> c, d, two pointers -> O(n)
// O(n^3)
// two for loops -> two pointers techniques -> 
// -> hashtable ->  Dictionary<int, List<int[]>
// two sum -> O(n^2), put into hashtable -> dictionary , 22, for each pair in 22 - key, 
// index -> unique -> 
// more than one pair -> key, store as list -> go over the list 
class Solution
{
    public static int[] FindArrayQuadruplet(int[] arr, int s)
    {
      // your code goes here
      if(arr == null || arr.Length < 4)
      {
        return new int[]; 
      }
      
      var twoSumTable = twoSumTable(arr); 
      
      // two sum - s/2 
      var half = s / 2; 
      foreach(var pair in twoSumTable)
      {
        var key = pair.Key; 
        if(key > half)
        {
          continue; 
        }
        
        var value = pair.Value; // 4,  list1
        var search = s - key; // 4, 
        var found = twoSumTable.ContainsKey(search); 
        if(!found)
        {
          continue; 
        }
        
        var list = twoSumTable[search]; 
        foreach(var item in list)
        {
          var quadruplet = new int[4]; 
          var isUnique = checkUnique(value, item, quadruplet);  // list1, list2, m, n -> m *n -> make sure unique 
          if(isUnique)
          {
            return quadruplet; 
          }
        }
      }
    }
  
    private static bool checkUnique(List<int[] list1, List<int[]> list2, int[] quadruplet)
    {
        var length1 = list1.Length; 
        var length2 = list2.Length; 
      
        for(var index1 = 0; index1 < length1; index1 ++)
        {
          for(var index2 = 0; index2 < length2; index2 ++)
          {
            var pair1 = list1[index1]; 
            var pair2 = list2[index2]; 
            
            var foundEqual = foundEqual(pair1, pair2); 
            if(!foundEqual)
            {
              // 
              return true;
            }
          }
        }
    }
  
    private static Dictionary<int, List<int[]>  twoSumTable(int[] arr)
    {
      // index1 < index2 
      var length = arr.Length; 
      
      var twoSumTable = new Dictionary<int, List<int[]>(); 
      
      for(var first = 0; first < length - 1; first ++)
      {
        for(var second = first + 1; second < length; second ++)
        {
          var value1 = arr[first]; 
          var value2 = arr[second]; 
          var twoSum = value1 + value2; 
          
          var valuePair = new int[]{first, second}; 
          
          if(twoSumTable.ConstainsKey(twoSum))
          {
            twoSumTable[twoSum].Add(valuePair); 
          }
          else
          {
            var list = new List<int[]>(); 
            list.Add(valuePair); 
            twoSumTable.Add(twoSum, list); 
          }
        }
      }
      
      return twoSumTable; 
    }

    static void Main(string[] args)
    {

    }
}