Given an array $A$, find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$? I have an array $A$ of $n$ integers. I need to find all quadruples $(i,j,k,\ell)$ such that $i&lt;j&lt;k&lt;\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$. What is the best way to do this? 

My attempt is an exhaustive search algorithm that works as follows:


Generate all quadruples $Q=\{(i,j,k,\ell): i&lt;j&lt;k&lt;\ell\}$.
For each quadruple $(i,j,k,\ell)\in Q$, verify $A[i]=A[k]$ and $A[j]=A[\ell]$.


This algorithm requires $$O\left(\binom{n}{4}\right)=O(n^4),$$ steps in the worst case. Can we do better? (Is this problem known somewhere?)

EDIT: I was using greedy instead of exhaustive search as Yuval mentioned.
Consider the absolute worst case, where every element is equal to every other element. This means that the algorithm has to output $n(n-1)(n-2)(n-3) \in O(n^4)$ quadruples. So in the worst case we can't do better. But often for problems like this it's useful to also consider cases where we don't have to output as much.

So let's do better. If you sort the data in $O(n \log n)$ (making sure to store the original indices) you can then in an $O(n)$ step find all equivalence classes. Then you can output all quadruples by first iterating over all possible pairs of equivalence classes and then iterate over all possible combinations of elements from those two equivalence classes.

Those last two steps are in theory $O(n^4)$, but are a lot smaller when the equivalence classes get smaller.