1428. Leftmost Column with at Least a One - cocoder39/coco39_LC GitHub Wiki

1428. Leftmost Column with at Least a One

Option 2 can be worse than option 1 if col is much large than row.

Option 1 binary search with optimization (upper bound of each search is no greater than known leftmost column)

O(rows * lgcols)

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        def binarySearch(left, right, row):
            while left + 1 < right:
                mid = left + (right - left) // 2
                val = binaryMatrix.get(row, mid)
                if val == 1:
                    right = mid
                else:
                    left = mid + 1
            
            if binaryMatrix.get(row, left) == 1:
                return left
            elif binaryMatrix.get(row, right) == 1:
                return right
            else:
                return -1
        
        rows, cols = binaryMatrix.dimensions()
        right_bound = cols - 1
        res = -1
        for i in range(rows):
            candidate = binarySearch(0, right_bound, i)
            if candidate != -1:
                res = candidate
                right_bound = candidate
        return res

Option 2 search space reduction

O(rows + cols)

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        rows, cols = binaryMatrix.dimensions()
        r, c = 0, cols - 1
        res = -1
        while r < rows and c >= 0:
            if binaryMatrix.get(r, c) == 1:
                res = c
                c -= 1
            else:
                r += 1
        return res