April 22, 2020
[30 day LeetCoding challenge, day 21] Leftmost Column with at Least a One
       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
                if (not found1):
                    start = middle+1
        return column

 

 

Problem descripion and image source: leetcode