leetcode 1428

solution 1, traverse

runtime 221ms, 9%

1428-1

1
2
3
4
5
6
7
8
9
10
11
12
13

def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
    rows, cols = binaryMatrix.dimensions()
    r, c = 0, cols - 1

    while r < rows and c >= 0:
        if binaryMatrix.get(r, c) == 0:
            r += 1
        else:
            c -= 1

    # If we never left the last column, it must have been all 0's.
    return c + 1 if c != cols - 1 else -1

runtime 111ms, 92.5%
1428-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# binary_search
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
    rows, cols = binaryMatrix.dimensions()

    # find the first on in column
    def find_one_columnwise(col):
        if col < 0:
            return -1
        for i in range(rows):
            if binaryMatrix.get(i, col) == 1:
                return i
        return -1

    # find first one in row
    def binary_search(row, col):
        left, right = 0, col
        while left < right:
            mid = (left+right)>>1
            if binaryMatrix.get(row,mid) == 0:
                left = mid + 1
            else:
                right = mid

        return left

    # start from last column
    col = cols -1
    # find the first 1 in col, record its row r
    while (r := find_one_columnwise(col)) >= 0:
        # do binary search, find the first one in this row r
        # and record its column, and prepare start the loop from column-1 again
        col = binary_search(r, col) -1

    return -1 if col == cols -1 else col+1