1428. Leftmost Column with at Least a One

Problem Statement

link: LeetCode.cn LeetCode A row-sorted binary matrix means that all elements are 0 or 1 and each row of the matrix 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 does not 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 the dimensions of the matrix as a list of 2 elements [rows, cols], which means the matrix is rows x cols. 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, the input will be the entire binary matrix mat. You will not have access to the binary matrix directly.

Example:

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

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

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

Constraints: rows == mat.length cols == mat[i].length 1 <= rows, cols <= 100 mat[i][j] is either 0 or 1. mat[i] is sorted in non-decreasing order.

Solution Approach

The solution involves starting from the top-right corner of the matrix and moving left if a 1 is found or moving down if a 0 is encountered, aiming to find the leftmost column with a 1.

Algorithm

1. Start from the top-right corner: Initialize the current position at the top-right corner of the matrix (row 0, column cols - 1).
2. Traverse the matrix: Move left if a 1 is found (to potentially find a leftmost 1), or move down if a 0 is encountered (to explore the next row).
3. Return the result: If a 1 is found, return the current column index; otherwise, return -1 if no 1 is found in the entire matrix.

Implement

    # """ # This is BinaryMatrix's API interface. # You should not implement it, or speculate about its implementation # """ #class BinaryMatrix(object): #    def get(self, row: int, col: int) -> int: #    def dimensions(self) -> list[]:
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        rows, cols = binaryMatrix.dimensions()
        smallest_index = cols
        for row in range(rows):
            lo = 0
            hi = cols - 1
            while lo < hi:
                mid = (lo + hi) // 2
                if binaryMatrix.get(row, mid) == 0:
                    lo = mid + 1
                else:
                    hi = mid
            if binaryMatrix.get(row, lo) == 1:
                smallest_index = min(smallest_index, lo)
        return -1 if smallest_index == cols else smallest_index

class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        rows, cols = binaryMatrix.dimensions()
        current_row = 0
        current_col = cols - 1

        while current_row < rows and current_col >= 0:
            if binaryMatrix.get(current_row, current_col) == 0:
                current_row += 1
            else:
                current_col -= 1
        
        return current_col + 1 if current_col != cols - 1 else -1

  

    
    

Twitter  facebook  Email