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 1:
Input: mat = [[0,0],[1,1]] Output: 0
Example 2:
Input: mat = [[0,0],[0,1]] Output: 1
Example 3:
Input: mat = [[0,0],[0,0]] Output: -1
Constraints:
rows == mat.lengthcols == mat[i].length1 <= rows, cols <= 100mat[i][j] is either 0 or 1.mat[i] is sorted in non-decreasing order.Problem Overview: You’re given a row-sorted binary matrix where each row contains only 0s followed by 1s. Access is restricted through the BinaryMatrix API (get and dimensions). The goal is to return the index of the leftmost column that contains at least one 1. If no such column exists, return -1.
Approach 1: Brute Force Scan (O(m × n) time, O(1) space)
Read every cell in the matrix using BinaryMatrix.get(row, col). Iterate row by row and column by column, tracking the smallest column index where a 1 appears. This approach ignores the sorted property of rows and performs up to m × n API calls. It works for very small matrices but quickly becomes inefficient when the number of columns grows.
Approach 2: Binary Search Per Row (O(m log n) time, O(1) space)
Each row is sorted (all 0s before 1s), which makes binary search a natural fit. For every row, run binary search to locate the first occurrence of 1. Track the smallest column index found across all rows. The key optimization is limiting the search range using the best column found so far. Once a row produces a left boundary smaller than the current answer, update it. This approach drastically reduces the number of get calls compared to brute force.
Approach 3: Top-Right Staircase Traversal (O(m + n) time, O(1) space)
Start at the top-right corner of the matrix. If the current cell is 1, move left because a smaller column might still contain a 1. If the current cell is 0, move down because all cells to the left in that row are also 0. This creates a staircase walk across the grid that visits at most m + n cells. The technique leverages both row sorting and the grid structure, making it the most API-efficient solution for this array-style matrix problem.
Recommended for interviews: Binary search per row demonstrates that you recognize the sorted-row constraint and can apply O(log n) search. Strong candidates usually mention the staircase traversal as a further optimization with O(m + n) time. Showing both approaches proves you understand the structure of the matrix and how to minimize expensive API calls.
First, we call BinaryMatrix.dimensions() to get the number of rows m and columns n of the matrix. Then for each row, we use binary search to find the column number j where the leftmost 1 is located. The smallest j value that satisfies all rows is the answer. If there is no such column, return -1.
The time complexity is O(m times log n), where m and n are the number of rows and columns of the matrix, respectively. We need to traverse each row, and use binary search within each row, which has a time complexity of O(log n). The space complexity is O(1).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(m × n) | O(1) | Baseline solution or when constraints are extremely small |
| Binary Search Per Row | O(m log n) | O(1) | When rows are sorted and random access via API is available |
| Top-Right Staircase Traversal | O(m + n) | O(1) | Optimal approach when matrix rows are sorted and minimizing API calls matters |
Leftmost column with atleast a one | Ladder approach | Leetcode • Techdose • 9,851 views views
Watch 9 more video solutions →Practice Leftmost Column with at Least a One with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor