LeetCoding Challenge 21/30. Leftmost Column with at Least a One

Posted on | In |
Words count in article: 506 | Reading time ≈ 2

题目

(This problem is an interactive problem.)

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

Given a row-sorted binary matrix binaryMatrix, return leftmost column index(0-indexed) with at least a 1 in it. If such index doesn’t exist, return -1.

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

  • BinaryMatrix.get(x, y) returns the element of the matrix at index (x, y) (0-indexed).
  • BinaryMatrix.dimensions() returns a list of 2 elements [n, m], which means the matrix is n * m.

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 you’re given the binary matrix mat as input in the following four examples. You will not have access the binary matrix directly.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

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

思路

Hint #1
(Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.

Hint #2
(Optimal Approach) Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down. If the value at p is 0, move down. If the value at p is 1, move left. Try to figure out the correctness and time complexity of this algorithm.

其实sorted二维数组的查找都可以通过此方法:
首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；否则每一次都在数组的查找范围中剔除一行或者一列，直到找到要查找的数字，或者查找范围为空。
时间复杂度为O(max(n,m))

代码

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
# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
#class BinaryMatrix(object):
#    def get(self, x, y):
#        """
#        :type x : int, y : int
#        :rtype int
#        """
#
#    def dimensions:
#        """
#        :rtype list[]
#        """

class Solution(object):
    def leftMostColumnWithOne(self, binaryMatrix):
        """
        :type binaryMatrix: BinaryMatrix
        :rtype: int
        """
        n, m = binaryMatrix.dimensions()
        res = -1
        row = 0
        col = m - 1
        while row < n and col >= 0:
            if binaryMatrix.get(row, col) == 1:
                res = col
                col -= 1
            else:
                row += 1
        return res