Leftmost Column with at Least a One solution and explanation
8 more videos on this problem
Leftmost column with atleast a one | Ladder approach | LeetcodeTechdose · 9:42 · 9K views
leftmost column with at least a one leetcode python | leetcode | Facebook interview questionthecodingworld · 7:20 · 3K views
Leftmost Column with at Least a One | LeetCode | Programming TutorialsProgramming Tutorials · 11:14 · 1K views
Leetcode 1428 Leftmost Column with at Least a OneRen Zhang · 7:05 · 1K views
LeetCode 1428. Leftmost Column with at Least a OneHappy Coding · 28:04 · 643 views
Facebook Coding Interview Question | Leetcode 1428 | Leftmost Column with at Least a OneWorkWithGoogler · 18:42 · 606 views
LEETCODE : Leftmost Column with at Least a One[EXPLANATION + CODE ]Anand Pandey · 16:44 · 500 views
Leetcode - 1428 | leftmost column with at least a oneCS Talks · 23:46 · 410 views
Day 21 - Leftmost Column with at Least a OneHot Rod Gaming · 2:48 · 360 views
The 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 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 isrows 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 either0or1.mat[i]is sorted in non-decreasing order.
Approach overview
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.
Solution
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).
# """
# This is BinaryMatrix's API interface.
# You should not implement it, or speculate about its implementation
# """
# class BinaryMatrix(object):
# def get(self, row: int, col: int) -> int:
# def dimensions(self) -> list[]:
class Solution:
def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
m, n = binaryMatrix.dimensions()
ans = n
for i in range(m):
j = bisect_left(range(n), 1, key=lambda k: binaryMatrix.get(i, k))
ans = min(ans, j)
return -1 if ans >= n else ans/**
* // 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> e = binaryMatrix.dimensions();
int m = e.get(0), n = e.get(1);
int ans = n;
for (int i = 0; i < m; ++i) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (binaryMatrix.get(i, mid) == 1) {
r = mid;
} else {
l = mid + 1;
}
}
ans = Math.min(ans, l);
}
return ans >= n ? -1 : ans;
}
}/**
* // 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) {
auto e = binaryMatrix.dimensions();
int m = e[0], n = e[1];
int ans = n;
for (int i = 0; i < m; ++i) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (binaryMatrix.get(i, mid)) {
r = mid;
} else {
l = mid + 1;
}
}
ans = min(ans, l);
}
return ans >= n ? -1 : ans;
}
};/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* class BinaryMatrix {
* get(row: number, col: number): number {}
*
* dimensions(): number[] {}
* }
*/
function leftMostColumnWithOne(binaryMatrix: BinaryMatrix) {
const [m, n] = binaryMatrix.dimensions();
let ans = n;
for (let i = 0; i < m; ++i) {
let [l, r] = [0, n];
while (l < r) {
const mid = (l + r) >> 1;
if (binaryMatrix.get(i, mid) === 1) {
r = mid;
} else {
l = mid + 1;
}
}
ans = Math.min(ans, l);
}
return ans >= n ? -1 : ans;
}/**
* // This is BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* class BinaryMatrix {
* public int Get(int row, int col) {}
* public IList<int> Dimensions() {}
* }
*/
class Solution {
public int LeftMostColumnWithOne(BinaryMatrix binaryMatrix) {
var e = binaryMatrix.Dimensions();
int m = e[0], n = e[1];
int ans = n;
for (int i = 0; i < m; ++i) {
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (binaryMatrix.Get(i, mid) == 1) {
r = mid;
} else {
l = mid + 1;
}
}
ans = Math.Min(ans, l);
}
return ans >= n ? -1 : ans;
}
}/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* type BinaryMatrix struct {
* Get func(int, int) int
* Dimensions func() []int
* }
*/
func leftMostColumnWithOne(binaryMatrix BinaryMatrix) int {
e := binaryMatrix.Dimensions()
m, n := e[0], e[1]
ans := n
for i := 0; i < m; i++ {
l, r := 0, n
for l < r {
mid := (l + r) >> 1
if binaryMatrix.Get(i, mid) == 1 {
r = mid
} else {
l = mid + 1
}
}
ans = min(ans, l)
}
if ans >= n {
return -1
}
return ans
}/**
* // This is the BinaryMatrix's API interface.
* // You should not implement it, or speculate about its implementation
* struct BinaryMatrix;
* impl BinaryMatrix {
* fn get(row: i32, col: i32) -> i32;
* fn dimensions() -> Vec<i32>;
* };
*/
impl Solution {
pub fn left_most_column_with_one(binaryMatrix: &BinaryMatrix) -> i32 {
let e = binaryMatrix.dimensions();
let m = e[0] as usize;
let n = e[1] as usize;
let mut ans = n;
for i in 0..m {
let (mut l, mut r) = (0, n);
while l < r {
let mid = (l + r) / 2;
if binaryMatrix.get(i as i32, mid as i32) == 1 {
r = mid;
} else {
l = mid + 1;
}
}
ans = ans.min(l);
}
if ans >= n {
-1
} else {
ans as i32
}
}
}Complexity analysis
| 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 |
Frequently asked questions
Is Leftmost Column with at Least a One easy or hard?
LeetCode classifies the problem as Medium difficulty. The challenge comes from recognizing the sorted-row structure and optimizing API calls rather than performing a full matrix scan.
Leftmost Column with at Least a One Python/Java solution
Most implementations call BinaryMatrix.get within either a binary search loop or a top-right traversal loop. Python and Java solutions both maintain row and column pointers while minimizing API calls. Time complexity is typically O(m log n) or O(m + n) depending on the strategy.
How to solve Leftmost Column with at Least a One in O(m + n)?
Start from the top-right cell of the matrix. If BinaryMatrix.get(row, col) returns 1, move left to search for an earlier column containing 1. If it returns 0, move down to the next row. This staircase walk guarantees at most m + n steps.
What is the best approach for Leftmost Column with at Least a One?
The most efficient approach is the top-right staircase traversal with O(m + n) time and O(1) space. Start at the top-right corner of the matrix and move left if you see a 1 or down if you see a 0. This strategy exploits the row-sorted property and minimizes BinaryMatrix API calls.
Is Leftmost Column with at Least a One asked at Google/Amazon/Meta?
This problem pattern appears in interviews at companies like Google and Meta, especially when testing matrix traversal and API-constrained problems. Interviewers expect candidates to leverage the sorted-row property rather than scanning the entire grid.
What data structure is used in Leftmost Column with at Least a One?
The problem operates on a binary matrix accessed through an interactive BinaryMatrix API. The main techniques involve binary search and matrix traversal, both relying on the sorted property of rows.
What is the time complexity of Leftmost Column with at Least a One?
The optimal solution runs in O(m + n) time where m is the number of rows and n is the number of columns. A common alternative uses binary search on each row, giving O(m log n) time. Both solutions use O(1) extra space.