4 sum - array quadruplet - mock interview practice - less than 35 minutes, pass all test cases. Time complexity - O(n^2), space complexity - O(n^2), compared to O(n^3) using two pointers technique.

4sum_arrayQuadruplet_practice.cs

using System;
using System.Collections.Generic; 

class Solution
{
    public static int[] FindArrayQuadruplet(int[] arr, int s) // [3, 2, 1, 4, 5] -> given sum: 12 = 1 + 2 + 4 + 5
    {
      if(arr == null || arr.Length < 4 ) // false 
      {
        return new int[0]; 
      }
      
      Array.Sort(arr); // [1, 2,3, 4, 5]
      
      var dictionary = saveTwoSumToDictionary(arr); // 
      
      int length = arr.Length; 
      
      for(int first = 0; first < length - 3; first ++) // 0, 1
      {
        for(int second = first + 1; second < length - 2; second++) // 1
        {
          var firstTwoSum = arr[first] + arr[second]; // 1 + 2 = 3
          var no1 = arr[first]; // 1
          var no2 = arr[second]; // 2
          
          var search = s - firstTwoSum; // 12 - 3 = 9 
          
          // search the dictionary 
          if(!dictionary.ContainsKey(search)) 
          {
            continue; 
          }
          
          // go over the list to find one 
          var options = dictionary[search]; 
          foreach(int[] pair in options)
          {
            // check very simple logic: 
            var no3 = pair[0];
            var no4 = pair[1]; 
            
            var index3 = pair[2]; 
            
            var unique = no2 <= no3 && second < index3; // same value but index is different, include duplicate number case 
            if(unique)
            {
              return new int[]{no1, no2, no3, no4}; // no1 < no2 < no3 < no4 , duplicate number -> index are different 
            }
          }
        }
      }
      
      return new int[0];       
    }

    private static Dictionary<int, List<int[]>> saveTwoSumToDictionary(int[] arr) // [1,2, 3, 4, 5]
    {
      var twoSum = new Dictionary<int, List<int[]>>(); // 
      
      int length = arr.Length; // 5
      for(int i = 0; i < length - 1; i++) // 0 - 3 , 1, 2, 3, 4
      {
        for(int j = i + 1; j < length; j++) // 1, 2, 
        {
          var no1 = arr[i]; 
          var no2 = arr[j]; 
          
          var sum = no1 + no2; // 3
          
          if(twoSum.ContainsKey(sum)) // 5 , [1,4], [2, 3]
          {
            twoSum[sum].Add(new int[]{no1, no2, i, j}); 
          }
          else 
          {
            var newList = new List<int[]>(); 
            newList.Add(new int[]{no1, no2, i, j}); 
            twoSum.Add(sum, newList); 
          }
        }
      }
      
      return twoSum; 
      
    }
  
    static void Main(string[] args)
    {

    }
}
// [2, 7, 4, 0, 9, 5, 1, 3], s = 20 
// sort the array -> O(nlogn)
//[0, 1,2, 3, 4, 5,7, 9 ] sorted the array 
// two sum -> dictionary , key -> 1, 2, 3, n^2 pair -> 
// 4 sum -> 
// first two numbers  a < b < c < d, all possible (a, b), look up dictionary for the value s - a - b
// see if there is any entry -> int[], size is 2, c < d, int[0]
// b < int[0], a < b < c < d -> list of pair -> go over the list -> 
// space -> n^2 -> , O(n^2) -> look up dictionary -> O(1) -> O(size of list)

Fix a series of compiler errors:

1. First add package on line 2: using System.Collections.Generic;
2. Line 30, it should be ContainsKey not Contains
3. Line 54, return int[0]; -> return new int[0];
   Whiteboard testing, I found a bug in my design, so I added two extra elements in the array on line 78 to make sure that index of numbers is unique.