Skip to main content
Talentd

Leftmost Column with at Least a One - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchMatrixInteractive10 min readAsked at: Meta, SAP, Uber
Practice this problem

Problem Statement

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

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

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(m × n)O(1)Baseline solution or when constraints are extremely small
Binary Search Per RowO(m log n)O(1)When rows are sorted and random access via API is available
Top-Right Staircase TraversalO(m + n)O(1)Optimal approach when matrix rows are sorted and minimizing API calls matters

Video Solution

LeetCode Day 21 - Interactive Grid (Leftmost Column with 1) • Errichto Algorithms • 13,518 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Leftmost Column with at Least a One with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays