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.
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
