Problem

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 theleftmost 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.

Examples

Example 1:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1400-1499/1428.Leftmost%20Column%20with%20at%20Least%20a%20One/images/untitled-
diagram-5.jpg)
Input: mat = [[0,0],[1,1]]
Output: 0

Example 2:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1400-1499/1428.Leftmost%20Column%20with%20at%20Least%20a%20One/images/untitled-
diagram-4.jpg)
Input: mat = [[0,0],[0,1]]
Output: 1

Example 3:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1400-1499/1428.Leftmost%20Column%20with%20at%20Least%20a%20One/images/untitled-
diagram-3.jpg)
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

Method 1 – Top-Right Greedy Traversal

Intuition

Since each row is sorted, we can start from the top-right corner and move left if we see a 1, or down if we see a 0. This way, we minimize the number of BinaryMatrix.get calls and efficiently find the leftmost column with a 1.

Approach

  1. Get the dimensions of the matrix.
  2. Start at the top-right corner (row 0, col n-1).
  3. While within bounds:
    • If the current cell is 1, update the answer and move left.
    • If the current cell is 0, move down.
  4. If no 1 is found, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * // This is the BinaryMatrix's API interface.
 * // You should not implement it, or speculate about its implementation
 * class BinaryMatrix {
 *   public:
 *     int get(int row, int col);
 *     vector<int> dimensions();
 * };
 */
class Solution {
public:
    int leftMostColumnWithOne(BinaryMatrix &binaryMatrix) {
        vector<int> dim = binaryMatrix.dimensions();
        int rows = dim[0], cols = dim[1];
        int ans = -1, r = 0, c = cols - 1;
        while (r < rows && c >= 0) {
            if (binaryMatrix.get(r, c) == 1) {
                ans = c;
                --c;
            } else {
                ++r;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// type BinaryMatrix interface {
//     Get(row, col int) int
//     Dimensions() []int
// }
func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
    dim := binaryMatrix.Dimensions()
    rows, cols := dim[0], dim[1]
    ans, r, c := -1, 0, cols-1
    for r < rows && c >= 0 {
        if binaryMatrix.Get(r, c) == 1 {
            ans = c
            c--
        } else {
            r++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * // 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();
 * }
 */
class Solution {
    public int leftMostColumnWithOne(BinaryMatrix binaryMatrix) {
        List<Integer> dim = binaryMatrix.dimensions();
        int rows = dim.get(0), cols = dim.get(1);
        int ans = -1, r = 0, c = cols - 1;
        while (r < rows && c >= 0) {
            if (binaryMatrix.get(r, c) == 1) {
                ans = c;
                c--;
            } else {
                r++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// interface BinaryMatrix {
//     fun get(row: Int, col: Int): Int
//     fun dimensions(): List<Int>
// }
class Solution {
    fun leftMostColumnWithOne(binaryMatrix: BinaryMatrix): Int {
        val (rows, cols) = binaryMatrix.dimensions()
        var ans = -1
        var r = 0
        var c = cols - 1
        while (r < rows && c >= 0) {
            if (binaryMatrix.get(r, c) == 1) {
                ans = c
                c--
            } else {
                r++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# class BinaryMatrix:
#     def get(self, row: int, col: int) -> int: ...
#     def dimensions(self) -> list[int]: ...
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: 'BinaryMatrix') -> int:
        rows, cols = binaryMatrix.dimensions()
        ans = -1
        r, c = 0, cols - 1
        while r < rows and c >= 0:
            if binaryMatrix.get(r, c) == 1:
                ans = c
                c -= 1
            else:
                r += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// struct BinaryMatrix;
// impl BinaryMatrix {
//     fn get(&self, row: i32, col: i32) -> i32;
//     fn dimensions(&self) -> Vec<i32>;
// }
impl Solution {
    pub fn left_most_column_with_one(binary_matrix: &BinaryMatrix) -> i32 {
        let dim = binary_matrix.dimensions();
        let (rows, cols) = (dim[0], dim[1]);
        let (mut r, mut c) = (0, cols - 1);
        let mut ans = -1;
        while r < rows && c >= 0 {
            if binary_matrix.get(r, c) == 1 {
                ans = c;
                c -= 1;
            } else {
                r += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// interface BinaryMatrix {
//     get(row: number, col: number): number;
//     dimensions(): number[];
// }
class Solution {
    leftMostColumnWithOne(binaryMatrix: BinaryMatrix): number {
        const [rows, cols] = binaryMatrix.dimensions();
        let ans = -1, r = 0, c = cols - 1;
        while (r < rows && c >= 0) {
            if (binaryMatrix.get(r, c) === 1) {
                ans = c;
                c--;
            } else {
                r++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(rows + cols), since we move at most rows down and cols left.
  • 🧺 Space complexity: O(1), only a few variables are used.