Leftmost Column With At Least A One - Leetcode Solution

Problem 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 the index (0-indexed) of the leftmost column with a 1 in it. If such an 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(row, col) returns the element of the matrix at index (row, col) (0-indexed). BinaryMatrix.dimensions() returns a list of 2 elements [rows, cols], which means the matrix is rows * cols.

Example 1:

Input: binaryMatrix = [[0,0],[1,1]] Output: 0

Example 2:

Input: binaryMatrix = [[0,0],[0,1]] Output: 1

Example 3:

Input: binaryMatrix = [[0,0],[0,0]] Output: -1

Constraints:

1 <= binaryMatrix.length, binaryMatrix[i].length <= 100 binaryMatrix[i][j] is either 0 or 1. binaryMatrix[i] is sorted in non-decreasing order.

Solution:

We notice that the matrix is sorted in non-decreasing order. Therefore, we can use a binary search to traverse each row of the given matrix to find the leftmost column with 1.

We traverse each row of the given matrix and for each row, we use binary search to find the leftmost 1 in that row. If we find a 1 in a particular row, we update the minimum_index_seen_so_far until we reach the last row. In case we do not find any 1 in a given row, we can skip that row since we want to find the leftmost 1. This way, we reduce the search space and find the leftmost column with 1 efficiently.

Let's see the Python code implementation of this approach:

class Solution: def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int: rows, cols = binaryMatrix.dimensions() minimum_index_seen_so_far = cols - 1 for row_index in range(rows): left, right = 0, cols - 1 while left <= right: mid = (left + right) // 2 if binaryMatrix.get(row_index, mid) == 1: minimum_index_seen_so_far = min(minimum_index_seen_so_far, mid) right = mid - 1 else: left = mid + 1 if minimum_index_seen_so_far == cols - 1: return -1 return minimum_index_seen_so_far

The time complexity of this solution is O(m*log(n)) where m is the number of rows and n is the number of columns in the binary matrix. The space complexity of this solution is O(1) since we are using a constant amount of extra space.

1