Equal

Given an array A of integers, find the index of values that satisfy A + B = C + D, where A,B,C & D are integers values in the array

Note:

1) Return the indices `A1 B1 C1 D1`, so that 
  A[A1] + A[B1] = A[C1] + A[D1]
  A1 < B1, C1 < D1
  A1 < C1, B1 != D1, B1 != C1 

2) If there are more than one solutions, 
   then return the tuple of values which are lexicographical smallest. 

Assume we have two solutions
S1 : A1 B1 C1 D1 ( these are values of indices int the array )  
S2 : A2 B2 C2 D2

S1 is lexicographically smaller than S2 iff
  A1 < A2 OR
  A1 = A2 AND B1 < B2 OR
  A1 = A2 AND B1 = B2 AND C1 < C2 OR 
  A1 = A2 AND B1 = B2 AND C1 = C2 AND D1 < D2

Example:

Input: [3, 4, 7, 1, 2, 9, 8]
Output: [0, 2, 3, 5] (O index)

If no solution is possible, return an empty list.

Method:

Similar to 4 sum

Solution:

Time: O(N^2)
Space: O(N)

public class Solution {
    static class Pair {
        int x;
        int y;
        
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
     public int compare(ArrayList<Integer> A, ArrayList<Integer> B) {
        for (int i = 0; i < A.size(); i ++) {
            int a = A.get(i);
            int b = B.get(i);
            if (a < b) {
                return -1;
            } else if (a > b) {
                return 1;
            }
        }
        return 0;
    }
    
    public ArrayList<Integer> equal(ArrayList<Integer> A) {
        ArrayList<Integer> result = new ArrayList<>();
        Map<Integer, Pair> map = new HashMap<>();
        for (int j = 1; j < A.size(); j ++) {
            for (int i = 0; i < j; i ++) {
                int sum = A.get(i) + A.get(j);
                if (map.containsKey(sum) && map.get(sum).x < i && map.get(sum).y != i && map.get(sum).y != j) {
                    Pair p = map.get(sum);
                    ArrayList<Integer> candidate = new ArrayList<>();
                    candidate.add(p.x);
                    candidate.add(p.y);
                    candidate.add(i);
                    candidate.add(j);
                    if (result.isEmpty()) {
                        result = candidate;
                    } else if (compare(candidate, result) < 0) {
                        result = candidate;
                    }
                }
                if (!map.containsKey(sum)) {
                    map.put(sum, new Pair(i, j));
                }
            }
        }
        return result;
    }
}