Problem description:

(This problem is an interactive problem.)

A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix is sorted in non-decreasing order.

Given a row-sorted binary matrix binaryMatrix, return the index (0-indexed) of the leftmost column with a 1 in it. If such an index does not exist, return -1.

You can’t access the Binary Matrix directly. You may only access the matrix using a BinaryMatrix interface:

  • BinaryMatrix.get(row, col) returns the element of the matrix at index (row, col) (0-indexed).
  • BinaryMatrix.dimensions() returns the dimensions of the matrix as a list of 2 elements [rows, cols], which means the matrix is rows x cols.

Submissions making more than 1000 calls to BinaryMatrix.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

For custom testing purposes, the input will be the entire binary matrix mat. You will not have access to the binary matrix directly.

Example 1:

https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-5.jpg

1
2
Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-4.jpg

1
2
Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-3.jpg

1
2
Input: mat = [[0,0],[0,0]]
Output: -1

Example 4:

https://assets.leetcode.com/uploads/2019/10/25/untitled-diagram-6.jpg

1
2
Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1

Constraints:

  • rows == mat.length
  • cols == mat[i].length
  • 1 <= rows, cols <= 100
  • mat[i][j] is either 0 or 1.
  • mat[i] is sorted in non-decreasing order.

Solution:

Linear search

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/782eb2ba-5324-4c42-83bc-8b90b5b1cf39/Untitled.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# """
# 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:
        grid = binaryMatrix.dimensions()
        m, n = grid[0], grid[1]
        res = -1
        
        r, c = 0, n-1
        while r < m and c >= 0:
            if binaryMatrix.get(r,c) == 1:
                res = c
                c -= 1
            else:
                r += 1
        return res

time complexity: $O(M+N)$
space complexity: $O(1)$

Binary search:

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/6317458e-79c3-47ae-9137-2bc40826fcb7/IMG_9488.heic

Use binary search to find the mid column

Find if there’s 1 in the column by walking through rows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        # binary search
        # locate a row using binary search
        # check if there's 1 in the column 
        grid = binaryMatrix.dimensions()
        m, n = grid[0], grid[1]
        res = -1
        left, right = 0, n-1
        while left <= right:
            mid_col = left + (right-left)//2
            if self.existOneInColumn(binaryMatrix, m, mid_col):
                res = mid_col
                right = mid_col-1
            else:
                left = mid_col+1
        return res
    
    def existOneInColumn(self, binaryMatrix, m, c):
        for r in range(0, m):
            if binaryMatrix.get(r, c):
                return True
        return False

time complexity: $O(MlogN)$
space complexity: $O(1)$
reference:
related problem: