April 22, 2020 ```       Input: mat = [[0,0,0,1],[0,0,1,1],[0,1,1,1]]
Output: 1```

### Description:

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 `[m, n]`, which means the matrix is `m * n`.

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.

Hints:

1. (Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.
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.

### Solution:

``````# https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3306/

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

class Solution:
def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
m, n = binaryMatrix.dimensions()
column = -1

# Initiate initial row to show last seen row
row = 0

# start and end to show starting and ending
# column values that we want to search
start = 0
end = n

# Break condition for binary search
while(start != end):
middle = start + (end - start) // 2
middle_el = binaryMatrix.get(row, middle)

# if middle element is 1 then move left in the row
# and set end point to middle of the row
if(middle_el == 1):
end = middle
column = middle
# if middle element is 0 then check middle elements
# of the remaining rows
else:
found1 = False
for i in range(row+1, m):
el = binaryMatrix.get(i, middle)
# if 1 found in any row set that row as starting row
if(el == 1):
row = i
end = middle
column = middle
found1 = True
break
start = middle+1
return column``````

Problem descripion and image source: leetcode

Recent Posts
Categories
Archive
Tags