LeetCode 1428: Leftmost Column with at Least a One

Explanation

To find the leftmost column with at least a one in a binary matrix, we can start from the top-right corner and move left or down based on the value in each cell. This way, we can gradually narrow down the potential column with at least one in the matrix.

1. Start at the top-right corner of the matrix.
2. If the current cell value is 0, move down one row.
3. If the current cell value is 1, move left one column.
4. Repeat steps 2 and 3 until we reach the bottom-left corner of the matrix.

The key idea is to leverage the properties of a sorted binary matrix to optimize the search for the leftmost column with a one.

• Time complexity: O(rows + columns)
• Space complexity: O(1)

class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dimensions = binaryMatrix.dimensions();
        int rows = dimensions.get(0);
        int columns = dimensions.get(1);
        
        int currentRow = 0;
        int currentColumn = columns - 1;
        int leftmostColumn = -1;
        
        while (currentRow < rows && currentColumn >= 0) {
            if (binaryMatrix.get(currentRow, currentColumn) == 1) {
                leftmostColumn = currentColumn;
                currentColumn--;
            } else {
                currentRow++;
            }
        }
        
        return leftmostColumn;
    }
}