Problem statement

https://binarysearch.com/problems/Binary-Matrix-Leftmost-One/

Solution

One way to solve is binary search. However we can do better. Start form the top right corner and move only left or down.

Complexity

It is O(m + n) for time and O(1) for space.

Code

class Solution:
    def solve(self, M):
        if not M: return -1
        m, n = len(M), len(M[0])
        r, c = 0, n - 1
        ans = -1

        while r < m and c >= 0:
            if M[r][c] == 1:
                ans = c
                c -= 1
            else:
                r += 1
        return ans