Problem Statement

You are given a binary matrix (only 0s and 1s) binaryMatrix where:

• Each row is sorted in non-decreasing order (0s followed by 1s).
• You need to find the leftmost column index (0-based) that contains at least one 1.
• If no such column exists, return -1.

You can access the matrix only through an API:

int get(int row, int col)   // returns the value at row, col
List<Integer> dimensions() // returns [rows, cols]

Goal: Minimize the number of get() calls.

Example

Input:
binaryMatrix = [
  [0,0,0,1],
  [0,0,1,1],
  [0,1,1,1]
]
Output: 1
Explanation: Column 1 is the leftmost column containing a 1.

Key Observations

• Rows are sorted. So all 1s in a row appear to the right of 0s.
• You can start from the top-right corner:
  • If you see 1, move left (maybe there is a 1 further left).
  • If you see 0, move down (this row has no 1s before this column).
• This ensures O(rows + cols) time complexity.

Approach: Top-Right Pointer

1. Get the matrix dimensions: rows and cols.
2. Initialize:
   • row = 0 (top row)
   • col = cols - 1 (rightmost column)
3. Initialize leftmostCol = -1 (default if no 1 found)
4. While row < rows and col >= 0:
   • If binaryMatrix.get(row, col) == 1:
     • Update leftmostCol = col
     • Move left: col--
   • Else:
     • Move down: row++
5. Return leftmostCol.

Java Code

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface BinaryMatrix {
 *     public int get(int row, int col) {}
 *     public List<Integer> dimensions() {}
 * }
 */

import java.util.List;

public class LeftmostColumnWithOne {

    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dims = binaryMatrix.dimensions();
        int rows = dims.get(0);
        int cols = dims.get(1);

        int row = 0;
        int col = cols - 1;
        int leftmostCol = -1;

        while (row < rows && col >= 0) {
            if (binaryMatrix.get(row, col) == 1) {
                leftmostCol = col; // Update the leftmost 1
                col--;             // Move left
            } else {
                row++;             // Move down
            }
        }

        return leftmostCol;
    }
}

Dry Run Example

Input Matrix

[0, 0, 0, 1]
[0, 0, 1, 1]
[0, 1, 1, 1]

• Start at row=0, col=3 → value = 1 → update leftmostCol=3, move left col=2
• row=0, col=2 → value = 0 → move down row=1
• row=1, col=2 → value = 1 → update leftmostCol=2, move left col=1
• row=1, col=1 → value = 0 → move down row=2
• row=2, col=1 → value = 1 → update leftmostCol=1, move left col=0
• row=2, col=0 → value = 0 → move down row=3 → exit loop

Return: 1