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.


  • 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

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

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.

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


Credits To:

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

## Blog link:
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
                    l = m + 1
            if arr[i][r] == 1:
                leftmost = min(leftmost, r)
                leftmost = min(leftmost, r+1)
        return leftmost

Share It, If You Like It.

Leave a Reply

Your email address will not be published.