Watch 10 video solutions for Leftmost Column with at Least a One, a medium level problem involving Array, Binary Search, Matrix. This walkthrough by Techdose has 9,851 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |