Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest to a given value $q$. The restriction of memory is $\mathcal{O}(n)$. It is not allowed to change a given matrix.

The naive approach is $\mathcal{O}(n^4)$ brute force algorithm.

Also I can propose $\mathcal{O}(n^3)$ algorithm. Which use the following idea. Let we have two sorted arrays $c_1\leq c_2\le \cdots \leq c_{k}$ and $d_1\leq d_2\le \cdots \leq d_s$ and we need to find a sum of the form $c_i$ + $d_j$ nearest to a given $q$. We can do this by $\mathcal{O}(k+s)$ algorithm by imaginary merging two arrays: $$ c_1\leq c_2\leq \cdots \le c_{k}; \ \ q-d_s\leq q-d_{s-1}\leq \cdots\le q-d_{1} $$ in one array. So to solve the problem we can iterate the set of row-pairs of our matrix and to use the above idea. Of course this algorithm will have a complexity $\mathcal{O}(n^3)$.

My question. How can we do this more effectively?


1 Answer 1


Try something like binary search since it is sorted i.e. check a[n/2,n]+a [n/2 +1,1] if equal done -smaller check the lower half -greater check the upper half (Keep the last checked value to compare how close with the next one) Probably O ( log n2)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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