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.

Description Hints 2 Solution Video 9:42

1428. Leftmost Column with at Least a One

Medium55.3% acceptance3 companiesPremium elsewhere, free here

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.

Asked at 3 companies

Uber SAP Meta

Topics

Hints open one at a time

Hint 1

1. (Binary Search) For each row do a binary search to find the leftmost one on that row and update the answer.

Hint 2

2. (Optimal Approach) Imagine there is a pointer p(x, y) starting from top right corner. p can only move left or down. If the value at p is 0, move down. If the value at p is 1, move left. Try to figure out the correctness and time complexity of this algorithm.

9:42

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[0,0],[1,1]]

Input

[[0,0],[0,1]]

Input

[[0,0],[0,0]]

Your code is saved on this device.Solution