LintCode: Leftmost One

Leftmost One

Similar Problems:

Given a 2D array, and each line has only 0 and 1, the front part is 0, and the latter part is 1. Find the number of columns in the leftmost 1 of all the rows in the array.

Notice

• The number of rows in the array and the number of columns do not exceed 1000
• In order to limit the time complexity, your program will run 50000 times

Example
Given arr = [[0,0,0,1],[1,1,1,1]], return 0.

```Explanation:
Arr[1][0] is the leftmost 1 in all rows and its column is 0.
```

Given arr = [[0,0,0,1],[0,1,1,1]], return 1.

```Explanation:
Arr[1][1] is the leftmost 1 in all rows and its column is 1.
```

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/leftmost-one
class Solution:
"""
@param arr: The 2-dimension array
@return: Return the column the leftmost one is located
"""
def getColumn(self, arr):
## Basic Ideas: binary search
## Complexity: Time O(m*log(n)), Space O(1)
row_count = len(arr)
if row_count == 0: return 0
col_count = len(arr[0])
leftmost = row_count
for i in range(row_count):
# binarysearch
l, r = 0, col_count-1
while l<r:
# find first 1
m = int(l+(r-l)/2)
if arr[i][m] == 1:
r = m
else:
l = m + 1
if arr[i][r] == 1:
leftmost = min(leftmost, r)
else:
leftmost = min(leftmost, r+1)
return leftmost
```

Share It, If You Like It.