The Art Gallery Guardian

Search in a sorted matrix with an oracle


Consider a infinite matrix MM. Another way to think about it is a function f:NNXf:\N\to \N\to X. A matrix MM is sorted if Mi,jMi,j+1M_{i,j}\leq M_{i,j+1} and Mi,jMi+1,jM_{i,j}\leq M_{i+1,j}.

Problem1

Given a sorted matrix MM, and an oracle that takes λ\lambda returns if a value is λ<λ\lambda <\lambda^* or λλ\lambda \geq \lambda^*. Find the largest value no larger than λ\lambda^*.

Assuming there are at most kk elements no larger than λ\lambda^*, and we know the smallest nn and mm such that Mi,j>λM_{i,j}>\lambda^* if i>ni>n or j>mj>m. Also, let tt be the smallest number such that Mt,t>λM_{t,t}>\lambda^*. One can see that tmin(n,m)t\leq \min(n,m) and k=O(max(n,m)2)k=O(\max(n,m)^2).

Let's first consider the case when nn and mm is known and nmn\leq m. It is Leetcode 240. Search a 2D Matrix II. However, our problem is more general, because comparison with λ\lambda^* can only be done through the oracle. Craig Gidney wrote about an optimal algorithm with O(nlogmn)O(n\log \frac{m}{n}) running time, matrix access algorithm. However, the oracle access is too large. There are times where the oracle access is slow. For example, when using it as a subroutine for finding a bottleneck kk-link path. There is an algorithm with optimal running time and O(log(nm))O(\log(nm)) oracle access.

Let's consider a special case, where n=m=2in=m=2^i for some ii. This case was shown in [1]. For each submatrix, the two vertices on the opposite diagonal indicates the largest and smallest element in the submatrix. Hence each matrix can be represented by two numbers, indicate the maximum and minimum. These numbers are called the representative of the matrix. The idea is we keep two numbers λ1\lambda_1 and λ2\lambda_2, such that we know λ[λ1,λ2]\lambda^*\in [\lambda_1,\lambda_2]. The algorithm keep partition the matrix into small matrices, updating λ1\lambda_1 and λ2\lambda_2, and discard matrices outside the range. We apply the following algorithm. Let RR consists of the multiset of representatives of the matrix, and RR' be the representatives that lies inside [λ1,λ2][\lambda_1,\lambda_2]. We find λ\lambda, the median of RR'. Test if λ<λ\lambda<\lambda^*. If so, then λ1\lambda_1 updates to λ\lambda, otherwise λ2\lambda_2 updates to λ\lambda. This step is done twice. Now, we split the matrices with more than one element into 44 equally sized matrices, and repeat the algorithm. Recall at all times, the matrices does not contain any element in [λ1,λ2][\lambda_1,\lambda_2] are discarded.

There is at most O(logn)O(\log n) iterations before range shrinks to a single element, hence at most O(logn)O(\log n) oracle calls. The difficulty is to show that the overall time is only O(n)O(n). Intuitively, in each iteration we quadruple the number of matrices, but we half it by two calls to the oracle. Therefore in logn\log n steps we obtain roughly 2logn=O(n)2^{\log n}=O(n) matrices. However, at this point, the matrices are all singletons, and no more matrix can be created. We will only decrease the number of matrices by each oracle call. Careful reader can trace the whole argument in Lemma 2.1 of [1].

For the more general case, one can find the proof in [2]. Note the proof is for selection, but one can easily modify it to work for search.

Now, nn and mm is not known, but we can quickly using exponential search to find it. Indeed, we just have to apply exponential search in the first row and first column using the oracle. This gives us an extra O(logn+logm)=O(lognm)O(\log n + \log m)=O(\log nm) oracle calls.

Let kk to be the number of elements no larger than λ\lambda^*. We can get running time relative to kk. Use exponential search until we find the first ii such that M2i,2i>λM_{2^i,2^i}>\lambda^*. So we can upper bound tt. Then one can solve the problem with 22 matrices. One t×kt\times k matrix and a k×tk\times t matrix. The total running time is therefore O(logk+tlogk/t)=O(tlogk)O(\log k+t\log k/t)=O(t\log k). In fact, we get O(logk)O(\log k) oracle calls and O(tlogk)O(t\log k) running time. Here we can take tt to be k\sqrt{k}, and obtain O(klogk)O(\sqrt{k}\log k) time.

Note if we relax on number of oracle calls. I know how to get a O(k)O(\sqrt{k}) running time.

Theorem2

Given λ\lambda^* and a n×mn\times m sorted matrix such that the iith row has kik_i elements no larger than xx. Let k=ikik=\sum_{i} k_i. We can find λ\lambda^* in O(ilog(ki+1ki+1))=O(nlogkn2)O(\sum_{i} \log (k_{i+1}-k_i+1) ) = O(n \log \frac{k}{n^2}) time.

The idea is simple, we do exponential search on each row to find the largest element no larger than λ\lambda^*, but we reuse information from the previous row. This gives us the running time O(ilog(ki+1ki+1))O(\sum_{i} \log (k_{i+1}-k_i+1) ). The main difficulty is to show why is is O(nlogkn2)O(n \log \frac{k}{n^2}).

Lemma3

If i=1nki=k\sum_{i=1}^n k_i=k, then i=1nlog(ki+1ki+1)=O(nlogk/n2)\sum_{i=1}^n \log (k_{i+1}-k_i+1)=O(n\log k/n^2).

Once we show that, we can use the theorem to obtain O(k)O(\sqrt{k}) running time.

In fact, we can also get a very simple algorithm with running time O(hlog(k/h2))O(h \log(k/h^2)), where hh is the number of stairs in the staircase shape. However, it also uses O(hlog(k/h2)O(h\log(k/h^2) oracle calls. The idea is to use exponential search to find the boundary of the staircase, but we switch between boundaries: horizontal then vertical. It is open if we can obtain O(hlog(k/h2))O(h\log(k/h^2)) running time and O(logk)O(\log k) oracle calls.

1 Remark

There is an alternative algorithm which can be found in [3]. The alternative algorithm is quite close to a post about selection in a sorted matrix.

The careful reader might observe the known search algorithms follow the exact same structure as algorithms for selection. Indeed, we are doing selection but we do not know the rank of the element. Intuitively, many selection algorithm, the rank is only used to remove the correct set of candidates. Hence this suggest one can modify the algorithm to use the oracle call in place of the rank.

References

[1] G.N. Frederickson, S. Zhou, Optimal parametric search for path and tree partitioning, CoRR. abs/1711.00599 (2017).

[2] G. Frederickson, D. Johnson, Generalized selection and ranking: Sorted matrices, SIAM Journal on Computing. 13 (1984) 14–30 10.1137/0213002.

[3] R. Jacob, Binary search on two-dimensional data, Technische Universität München, 2008.

Posted by Chao Xu on .
Tags: algorithm, data structure.