LC 1428 [M] Leftmost Column with at Least a One - ALawliet/algorithms GitHub Wiki

intuitive? Y

gotcha:

  • keep in mind when we do while r < n_row it loops n_row times (1-indexed) but if we do while c > 0 it only loops n_col-1 times (0-indexed) so we need >= instead: while r < n_row and c >= 0 or while r <= n_row-1 and c >= 0
  • when looping rows with r be careful using r in binary search right pointer, we want binaryMatrix.get(row, m)

binary search leftmost on each row and store the min col

T: O(mlogn) = O(n_rows x log(n_cols))
S: O(1)

start at top-right and scan left-down

T: O(m+n)
S: O(1)

# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
#class BinaryMatrix(object):
#    def get(self, row: int, col: int) -> int:
#    def dimensions(self) -> list[]:
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        n_rows, n_cols = binaryMatrix.dimensions()
        leftmost_c = n_cols

        def binarysearch_first(A):
            l = 0
            r = n_cols # the right pointer is the leftmost so far
            while l < r:
                m = (l + r ) // 2
                if not binaryMatrix.get(row, m) == 1:
                    l = m + 1
                else:
                    r = m
            return l
        
        for row in range(n_rows):
            l = binarysearch_first(row)  
            leftmost_c = min(leftmost_c, l)
                
        return leftmost_c if leftmost_c != n_cols else -1
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        n_rows, n_cols = binaryMatrix.dimensions()
        r = 0
        c = n_cols - 1
        leftmost_col = -1

        # r <= n_rows-1
        while r < n_rows and c >= 0:
            if not binaryMatrix.get(r, c) == 1:
                r += 1 # move down
            else: # == 1
                leftmost_col = c # if we moved left then this has to be the leftmost so far
                c -= 1 # move left

        return leftmost_col