<p>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.</p>
<p><strong>Lemma 1.</strong> <em>There is an <span class="math-container">$O(n\log n)$</span>-time algorithm for the problem.</em></p>
<p><em>Proof sketch.</em>  The problem reduces (by sorting w.r.t. <span class="math-container">$A$</span> and negating <span class="math-container">$C$</span>) in <span class="math-container">$O(n \log n)$</span>-time to the following:</p>
<blockquote>
<p>Given a sequence <span class="math-container">$(b_1, c_1), (b_2, c_2), \ldots, (b_n, c_n)$</span> of points in the plane (with integer coordinates), is there a point <span class="math-container">$(b_j, c_j)$</span> that dominates some earlier point <span class="math-container">$(b_i, c_i)$</span> (that is, an <span class="math-container">$i&lt;j$</span> with <span class="math-container">$(b_i, c_i) &lt; (b_j, c_j)$</span>, coordinate-wise)?</p>
</blockquote>
<p>The algorithm considers the points <span class="math-container">$(b_j, c_j)$</span> in the order given, and checks each to see whether it dominates some previously considered <span class="math-container">$(b_i, c_i)$</span>.  As soon as it finds such a dominator, it stops and returns 'yes'.  If it never finds one, it returns 'no'</p>
<p>Suppose that the algorithm is considering a point <span class="math-container">$(b_j, c_j)$</span>, 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 <span class="math-container">$b_i$</span> and decreasing <span class="math-container">$c_i$</span> simultaneously.  The algorithm will maintain the previous points in, say, a balanced binary search tree, ordered accordingly.  When the next point <span class="math-container">$(b_j, c_j)$</span> is considered, by searching in this search tree, in <span class="math-container">$O(\log n)$</span> time, the algorithm can determine whether there is a previous point that is dominated by <span class="math-container">$(b_j, c_j)$</span>.</p>
<p>If there is, the algorithm halts and returns 'yes'.  Otherwise, the algorithm inserts <span class="math-container">$(b_j, c_j)$</span> in the appropriate place in the order and continues.</p>
<p>To finish we deal with the possibility that <span class="math-container">$(b_j, c_j)$</span> might be dominated by some previous point or points <span class="math-container">$(b_i, c_i)$</span>, as follows.  We can find all such points in time <span class="math-container">$O(\log n)$</span> per point, and simply remove them, because any future point that dominates such a point <span class="math-container">$(b_i, c_i)$</span> will also dominate <span class="math-container">$(b_j, c_j)$</span> (which we retain).  <span class="math-container">$~~~\Box$</span> ?</p>

CC BY-SA 4.0
2022-06-29T02:05:20.597Z
One can also find an O(n log n) time algorithm in Jon Bentley, "Multidimensional Divide and Conquer", Communications of the ACM, April 1980.
Ryan Williams
CC BY-SA 4.0
2022-06-29T02:08:17.037Z
+1 for @RyanWilliams (better) answer.
Neal Young
CC BY-SA 4.0
2022-06-29T02:16:05.860Z
Excellent answer! Thank you so much!!
karmanaut
CC BY-SA 4.0
2022-06-29T14:12:34.477Z
@RyanWilliams maybe you can convert your comment into an answer. Be sure I'll upvote it as well :-)
Hermann Gruber
CC BY-SA 4.0
2022-06-29T01:54:48.360Z
2022-06-29T01:54:48.360Z
Neal Young
<p>One can also find an <span class="math-container">$O(n \log n)$</span> time algorithm in Jon Bentley, &quot;Multidimensional Divide and Conquer&quot;, Communications of the ACM, April 1980.</p>

CC BY-SA 4.0
2022-06-30T20:55:38.737Z
2022-06-30T20:55:38.737Z
Ryan Williams
<p>Consider three arrays <span class="math-container">$A,B,C$</span> of size <span class="math-container">$N$</span> consisting of integers. I want to verify the following constraint: for any two indices <span class="math-container">$0 \leq i,j &lt; N$</span>, <span class="math-container">$A[i] &lt; A[j] \land B[i] &lt; B[j] \implies C[i] &lt; C[j]$</span>. The trivial algorithm here does the verification in <span class="math-container">$O(N^2)$</span> 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.</p>

<ds.algorithms><lower-bounds>
Quadratic lower bound
karmanaut
# Quadratic lower bound

(Asked by: username_0 on 2022-06-28)

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.

**Tags:** ds.algorithms, lower-bounds

---

## 2 answers

### Answer by username_2 on 2022-06-30. Score: 7 | Accepted answer

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


---

### Answer by username_1 on 2022-06-29. Score: 9

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 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$ ?

> **Comments:**
> **username_2**: One can also find an O(n log n) time algorithm in Jon Bentley, "Multidimensional Divide and Conquer", Communications of the ACM, April 1980.  
> **username_1**: +1 for @RyanWilliams (better) answer.  
> **username_0**: Excellent answer! Thank you so much!!  
> **username_3**: @RyanWilliams maybe you can convert your comment into an answer. Be sure I'll upvote it as well :-)  

---

