2
$\begingroup$

I have an array $A$ of $n$ integers. I need to find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\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<j<k<\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.

$\endgroup$
  • 1
    $\begingroup$ There is nothing greedy about your algorithm. It goes by the name exhaustive search. $\endgroup$ – Yuval Filmus Apr 7 '18 at 15:43
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How long would it take to decide whether any solution exists? What is the running time of listing all solutions if there are $m$ of them? $\endgroup$ – Yuval Filmus Apr 7 '18 at 15:43
  • $\begingroup$ @YuvalFilmus In the worst case I believe it takes $O(n^2)$ time to decide whether any solution exists (consider the case of $n/2$ equivalence classes without any solutions, like palindromic input $01233210$). I don't know what the worst case runtime is with $m$ solutions. $\endgroup$ – orlp Apr 7 '18 at 16:19
2
$\begingroup$

As orlp mentions in their answer, you can't do better than $O(n^4)$ in the worst case, since there could be $\binom{n}{4}$ many solutions (i.e., quadruples). We can improve on that in two regards:

  1. Find a faster algorithm for determining whether there is any solution.
  2. Find an algorithm whose running time depends gracefully on the number of solutions.

Here is an $O(n\log n)$ algorithm for finding out whether there is any solution at all. It also gives a good starting point for designing an "output-sensitive" algorithm (one whose running time depends on the number of solutions in a nice way).

The algorithm maintains two data structures:

  • The set $S$ of elements seen so far, initially empty.
  • A tree with labels on the vertices. One vertex, called the current vertex, is unlabeled. Initially the tree consists of an unlabeled root (which is the current vertex).

At each step we read one integer $x$. There are three possibilities:

  1. If $x \notin S$, we label the current vertex by $x$, add a new unlabeled child to this vertex (this is the new current vertex), and add $x$ to $S$.

  2. If $x \in S$, we delete the current vertex and start going up the tree. If we reach a vertex labeled $x$, we add to it a new unlabeled child, which is the new current vertex.

  3. If we don't find $x$, we halt, declaring "there is a solution".

After reading all integers, we halt, declaring "there is no solution".

Correctness. Let us suppose first that the algorithm announces that there is a solution. This happens after reading some element $x$ which is already in $S$, and so appears somewhere in the tree, say at node $v$. Let $p$ be the most common ancestor of $v$ and the current node, and suppose that $p$ is labeled $y$. The reader can check that the input array contains occurrences of $y,x,y,x$ (in that order).

Conversely, suppose that there is some solution, and consider the shortest prefix of the array in which there is a solution. Suppose that this prefix ends with the integer $x$, and that one of the solutions in this prefix is $y,x,y,x$ (there could be several, for example in the case $y,z,x,z,y,x$). Upon reading the final $x$, the set $S$ already contains $x$. However, $x$ cannot be an ancestor of the current node, due to the intervening $y$. Therefore a solution would be announced.

Running time. If we implement the set using a balanced binary tree, checking whether an integer is in $S$ takes time $O(\log n)$. If the read element is in $S$, then we go up the tree looking for it. Suppose first that we always find $x$ at an ancestor of the current node. Then we are traversing each edge of the final tree at most twice, and so overall these lookups together take $O(n)$. It can only happen once that $x$ is not found, and this lookup will also take $O(n)$.

All other actions take $O(1)$ per read value, so the total running time is $O(n\log n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If I want only distinct quadruples, can we do better than $O(n^4) $? Quadruples $(i,j,k,\ell)$ and $(i',j',k',\ell')$ are distincts iff $A[i]\neq A[i']$ or $A[j]\neq A[j']$ or $A[k]\neq A[k']$ or $A[\ell]\neq A[\ell']$ $\endgroup$ – zdm Apr 8 '18 at 22:24
  • $\begingroup$ In that case the number of potential solutions in the worst case is only $\Theta(n^2)$, so you can potentially do it faster. $\endgroup$ – Yuval Filmus Apr 8 '18 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.