First quadruplet - pass all test cases.

FirstQuadruplet_PassAllTestcase.py

def find_array_quadruplet(arr, s):
    if len(arr) < 4:
        return []
 
    pair_dict = {}
    # preprocess
    for i in xrange(0, len(arr)):
        for j in xrange(i+1, len(arr)):
            pair_sum = arr[i] + arr[j]
            if pair_sum not in pair_dict:
                pair_dict[pair_sum] = []
            # i < j
            pair_dict[pair_sum].append((i, j))
            
     # find
    for key, indices in pair_dict.iteritems():
        if s - key not in pair_dict:
            continue
          # s - key in dict
        s_indices = pair_dict[s-key]

        # two indices list
        for (i, j) in indices:
            for (k, r) in s_indices:
                if i != k and i != r and j != k and j != r:
                    # we have found the result
                    res = [arr[i], arr[j], arr[k], arr[r]]
                    return sorted(res)
                  
    return []