Problem statement

https://binarysearch.com/problems/Matrix-Search/

Solution

In fact it is enough brutforce to get AC here. However we can do better. For given x let us find number of elements which are <= x. We can answer this question in O(m + n), because we have special structure of matrix: on each step we can go down or to the right. Then we use binary search to find answer.

Complexity

It is O((m + n) * log(M)), where M is the biggest value of matrix.

Code

class Solution:
    def solve(self, M, k):
        def count(x):
            c = len(M[0]) - 1
            cnt = 0
            for row in M:
                while c >= 0 and row[c] > x:
                    c -= 1
                cnt += c + 1
            return cnt

        beg, end = M[0][0] - 1, M[-1][-1] + 1

        while beg + 1 < end:
            mid = (beg + end) //2
            if not count(mid) > k:
                beg = mid
            else:
                end = mid
        return beg + 1