12
$\begingroup$

Consider three arrays $A,B,C$ of size $N$ consisting of integers. I want to verify the following constraint: for any two indices $0 \leq i,j < N$, $A[i] < A[j] \land B[i] < B[j] \implies C[i] < C[j]$. The trivial algorithm here does the verification in $O(N^2)$ time. Is there a sub-quadratic algorithm for this problem? Any insight on proving a super linear lower bound or a (near) linear time algorithm would be greatly appreciated.

$\endgroup$
0

2 Answers 2

7
$\begingroup$

One can also find an $O(n \log n)$ time algorithm in Jon Bentley, "Multidimensional Divide and Conquer", Communications of the ACM, April 1980.

$\endgroup$
9
$\begingroup$

I think this works, but I don't have time to check the details carefully right now. I'll sketch the ideas and finish later, or someone else can check.

Lemma 1. There is an $O(n\log n)$-time algorithm for the problem.

Proof sketch. The problem reduces (by sorting w.r.t. $A$ and negating $C$) in $O(n \log n)$-time to the following:

Given a sequence $(b_1, c_1), (b_2, c_2), \ldots, (b_n, c_n)$ of points in the plane (with integer coordinates), is there a point $(b_j, c_j)$ that dominates some earlier point $(b_i, c_i)$ (that is, an $i<j$ with $(b_i, c_i) < (b_j, c_j)$, coordinate-wise)?

The algorithm considers the points $(b_j, c_j)$ in the order given, and checks each to see whether it dominates some previously considered $(b_i, c_i)$. As soon as it finds such a dominator, it stops and returns 'yes'. If it never finds one, it returns 'no'

Suppose that the algorithm is considering a point $(b_j, c_j)$, and has not yet terminated, so none of the previous points are dominators. First consider the case that, among all of the previous points, none dominates another. Then the points can be ordered naturally, by increasing $b_i$ and decreasing $c_i$ simultaneously. The algorithm will maintain the previous points in, say, a balanced binary search tree, ordered accordingly. When the next point $(b_j, c_j)$ is considered, by searching in this search tree, in $O(\log n)$ time, the algorithm can determine whether there is a previous point that is dominated by $(b_j, c_j)$.

If there is, the algorithm halts and returns 'yes'. Otherwise, the algorithm inserts $(b_j, c_j)$ in the appropriate place in the order and continues.

To finish we deal with the possibility that $(b_j, c_j)$ might be dominated by some previous point or points $(b_i, c_i)$, as follows. We can find all such points in time $O(\log n)$ per point, and simply remove them, because any future point that dominates such a point $(b_i, c_i)$ will also dominate $(b_j, c_j)$ (which we retain). $~~~\Box$ ?

$\endgroup$
4
  • 4
    $\begingroup$ One can also find an O(n log n) time algorithm in Jon Bentley, "Multidimensional Divide and Conquer", Communications of the ACM, April 1980. $\endgroup$ Jun 29 at 2:05
  • 3
    $\begingroup$ +1 for @RyanWilliams (better) answer. $\endgroup$
    – Neal Young
    Jun 29 at 2:08
  • $\begingroup$ Excellent answer! Thank you so much!! $\endgroup$
    – karmanaut
    Jun 29 at 2:16
  • $\begingroup$ @RyanWilliams maybe you can convert your comment into an answer. Be sure I'll upvote it as well :-) $\endgroup$ Jun 29 at 14:12

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.