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:**

- (Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.
- (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
if (not found1):
start = middle+1
return column
```

Problem descripion and image source: leetcode