[LeetCode][python3]Day21. Leftmost Column with at Least a One (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.22

1. My Solution

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        maxrow,maxcol=binaryMatrix.dimensions()
        state=0
        rp=maxcol-1
        lp=0
        row=0
        while row<maxrow and not state:
            state=state or binaryMatrix.get(row,rp)
            row+=1
        if not state:
            return -1
        
        while lp<=rp:
            mp=(rp+lp)//2
            row=state=0
            while row<maxrow and not state:
                state=state or binaryMatrix.get(row,mp)
                row+=1
            if not state:
                lp=mp+1
            else:
                rp=mp-1
        return lp

Explanation:

The key in this problem is the description “For each individual row of the matrix, this row is sorted in non-decreasing order”. Which means there is no row such like [1,0,0,1]. Every 1 in every row will be on the right part of that row such like [0,0,1,1].

We use binary search to select column, and use while to check every element in that column. While will exit if it founds 1 in that column or if it has checked every element in that column.

Binary selection will stop until it finds the border of “no 1 column” , where rp points to the last “no 1 column” and lp points to the first “1 column”.

The first time my run time is faster than all other solution. Yeah!