> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/equal.md).

# 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.

```java
public class Solution {
    public boolean isSmaller(ArrayList<Integer> ans, ArrayList<Integer> indices, int start) {
        if (start == ans.size())
            return false;
        if (indices.get(start) < ans.get(start)) {
            return true;
        }
        return indices.get(start) == ans.get(start) ? isSmaller(ans, indices, start + 1) : false;
    }

    public ArrayList<Integer> equal(ArrayList<Integer> A) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < A.size(); i++) {
            for (int j = i + 1; j < A.size(); j++) {
                int sum = A.get(i) + A.get(j);
                if (map.containsKey(sum)) {
                    if (map.get(sum).get(0) < i && map.get(sum).get(1) != i && map.get(sum).get(1) != j) {
                        ArrayList<Integer> indices = new ArrayList<>();
                        indices.addAll(Arrays.asList(map.get(sum).get(0), map.get(sum).get(1), i, j));
                        if (ans.size() == 0 || isSmaller(ans, indices, 0)) {
                            ans = indices;
                        }
                    }
                } else {
                    ArrayList<Integer> indices = new ArrayList<>();
                    indices.addAll(Arrays.asList(i, j));
                    map.put(sum, indices);
                }
            }
        }
        return ans;
    }
}
```