1
$\begingroup$

I have a $n\times n$ matrix called $M$, and two integers $k_\min$ and $k_\max$. Each row and each column of M is sorted in the increasing order.

I would like to know if there is way I can count the number of its elements which are inside $[k_\min, k_\max]$, using a $O(n)$ algorithm.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Which algorithms do you know? Why is this problem interesting to you? $\endgroup$ – Raphael Sep 17 '13 at 12:08
1
$\begingroup$

First, notice that you only need to know how to count the number of elements bigger than $k_{min}$, because then, by a very simple transformation, you can count the number of element smaller than $k_{max}$, and compute the desired result : since the set $A$ of element bigger than $k_{min}$ is of the form $[a;max]$, and the set $B$ of element smaller than $k_{max}$ is $[min;b]$, you have $|A \cap B| = |A| + |B| - n^2$

Now, find the last element smaller than $k_{min}$ on the last row, at column $c_0$. On this last row, exactly $n - c_0$ elements are bigger than $k_{min}$. On the row above, the last element smaller than $k_{min}$ has to be right to $c_0$, because otherwise, since $M$ is sorted on row and column, you would have a contradiction. Hence, in order to find the last element smaller than $k_{min}$ on this row, you can start at column $c_0$ and go right to find $c_1$. Then again, the number of elements bigger than $k_{min}$ on this row is $n - c_1$.

Repeating this process, you then sum the number of elements on each row to compute the result, and you'll scan only at most $2n$ elements since the path followed by the algorithm is a path from the point $(0,n-1)$ to the point $(n-1,0)$, going only up and left, and these kind of path have length $2n$. This is hence indeed an $\mathcal{O}(n)$ algorithm.

EDIT: details added

$\endgroup$
  • $\begingroup$ I don't get your first paragraph. Knowing $|A|$ and $|B|$, nothing is known about $|A \cap B|$ without further knowledge. Your algorithmic idea is nice, though, and can be adapted to solve the original problem in one pass by moving two points upwards in the matrix and summing over the difference in their positions. $\endgroup$ – Raphael Sep 17 '13 at 12:11
  • $\begingroup$ IMO. Your answer seems to be correct, but, I think you missed to mention two things : 1. Should also find biggest element which is smaller than $k_{max}$. 2. For counting (in O(n)) you should say subtract then index of largest and smallest element of each row +1, instead of simply saying count them (because may be someone iterate through them to count them, which is $O(n^2)$). $\endgroup$ – user742 Sep 17 '13 at 12:16
  • $\begingroup$ Is this not $\mathcal{O}(nlogn)$? If $k_{min},k_{max}$ are outside the matrix range.. Each find call in each row will be $\mathcal{O}(logn)$ by binary search, and there are $n$ rows. Am I missing anything? $\endgroup$ – Ioannis Sep 17 '13 at 15:50
  • 1
    $\begingroup$ @Raphael & Saeed: in this case, we can recover $|A \cap B|$ since $A$ is of the form $[a;\max]$ and $B$ is $[\min;b]$, hence $|A \cap B| = |A| + |B| - n^2$ $\endgroup$ – Tpecatte Sep 17 '13 at 17:06

Your Answer

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