Problem Description

You are given a binary matrix binaryMatrix with n rows and m columns. Each value in the matrix is either 0 or 1. Each row in the matrix is sorted in non-decreasing order (all the 0s come before 1s in every row).

Your task is to find the index (0-based) of the leftmost column that contains at least a single 1. If no such column exists (i.e., the matrix consists of all 0s), return -1.

• Each row is sorted: 0s first, then 1s.
• You cannot access the matrix directly; instead, you must use a provided API: get(row, col) to retrieve the value at a specific cell, and dimensions() to get the matrix size.
• The number of calls to get should be minimized.
• There is only one valid solution for each input.

Thought Process

At first glance, you might consider checking every cell in the matrix for a 1 and keeping track of the leftmost column index. However, since each row is sorted, we can do better than brute-force.

The key insight is that, because of the row-wise sorting, once you find a 1 in a row, all cells to the right will also be 1s. This means we can skip unnecessary checks and use a more efficient search strategy.

Instead of searching every cell, we can start from the top-right corner and systematically move left or down based on the value we find, which helps us quickly zero in on the leftmost column containing a 1.

Solution Approach

We use a stepwise linear search, starting from the top-right corner of the matrix:

1. Initialize: Get the matrix dimensions n (rows) and m (columns). Start at the top-right cell: row = 0, col = m - 1.
2. Iterate: While row < n and col >= 0:
   • If binaryMatrix.get(row, col) == 1, move left (decrement col by 1) because there might be a 1 further left.
   • If binaryMatrix.get(row, col) == 0, move down (increment row by 1) because this row doesn't have a 1 in this column or any to the left.
3. Track the leftmost column: Each time you move left, update your answer to the current column index.
4. Result: If you found any 1s, return the leftmost column index; otherwise, return -1.

This approach ensures we never visit the same cell twice and minimizes the number of API calls.

Example Walkthrough

Suppose binaryMatrix is:

    0 0 0 1
    0 0 1 1
    0 1 1 1
  

1. Start at (row=0, col=3): value is 1 → move left to col=2.
2. (row=0, col=2): value is 0 → move down to row=1.
3. (row=1, col=2): value is 1 → move left to col=1.
4. (row=1, col=1): value is 0 → move down to row=2.
5. (row=2, col=1): value is 1 → move left to col=0.
6. (row=2, col=0): value is 0 → move down to row=3 (out of bounds).

The leftmost column index where we found a 1 was at col=1. So, the answer is 1.

Time and Space Complexity

• Brute-force: Check every cell: O(n * m) time, O(1) space (since we only track the minimum column index).
• Optimized approach: At most n + m steps (each step moves either left or down). So time complexity is O(n + m), space is still O(1).
• This is much faster, especially for large matrices.

Summary

By leveraging the sorted property of each row, we avoid unnecessary checks and minimize API calls. The stepwise linear search from the top-right corner efficiently narrows down the leftmost column containing a 1, resulting in an elegant and optimal solution.

Code Implementation

# This assumes you are given a BinaryMatrix API with get and dimensions methods.
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix):
        n, m = binaryMatrix.dimensions()
        row, col = 0, m - 1
        answer = -1
        while row < n and col >= 0:
            if binaryMatrix.get(row, col) == 1:
                answer = col
                col -= 1
            else:
                row += 1
        return answer
      

// Assume BinaryMatrix is an interface with get() and dimensions() methods
class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        vector<int> dims = binaryMatrix.dimensions();
        int n = dims[0], m = dims[1];
        int row = 0, col = m - 1;
        int answer = -1;
        while (row < n && col >= 0) {
            if (binaryMatrix.get(row, col) == 1) {
                answer = col;
                col--;
            } else {
                row++;
            }
        }
        return answer;
    }
};
      

// Assume BinaryMatrix is an interface with get() and dimensions() methods
class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dims = binaryMatrix.dimensions();
        int n = dims.get(0), m = dims.get(1);
        int row = 0, col = m - 1;
        int answer = -1;
        while (row < n && col >= 0) {
            if (binaryMatrix.get(row, col) == 1) {
                answer = col;
                col--;
            } else {
                row++;
            }
        }
        return answer;
    }
}
      

/**
 * @param {BinaryMatrix} binaryMatrix
 * @return {number}
 */
var leftMostColumnWithOne = function(binaryMatrix) {
    const [n, m] = binaryMatrix.dimensions();
    let row = 0, col = m - 1;
    let answer = -1;
    while (row < n && col >= 0) {
        if (binaryMatrix.get(row, col) === 1) {
            answer = col;
            col--;
        } else {
            row++;
        }
    }
    return answer;
};