How hard is LeetCode 1428. Leftmost Column with at Least a One?

LeetCode 1428. Leftmost Column with at Least a One is rated Medium on LeetCode.

What is the time complexity of LeetCode 1428. Leftmost Column with at Least a One?

The Python solution on this page runs in O(m \times \log n), where m and n are the number of rows and columns of the matrix, respectively.

What is the space complexity of LeetCode 1428. Leftmost Column with at Least a One?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 1428. Leftmost Column with at Least a One cover?

LeetCode 1428. Leftmost Column with at Least a One is tagged Array, Binary Search, Interactive and Matrix on LeetCode.

Is LeetCode 1428. Leftmost Column with at Least a One a premium problem?

Yes. LeetCode 1428. Leftmost Column with at Least a One is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Leftmost Column with at Least a One — LeetCode 1428 Python Solution

MediumLeetCode PremiumArrayBinary SearchInteractiveMatrix

Problem: #1428
Pattern: Matrix and Grid
Reading time: 3 min
Source: leetcode.com

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.

Example

Input: mat = [[0,0],[1,1]]
Output: 0

Python solution

Python

# """
# 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

Complexity

Measure	Complexity
Time	O(m \times \log n), where m and n are the number of rows and columns of the matrix, respectively
Space	O(1) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1428. Leftmost Column with at Least a One is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1428. Leftmost Column with at Least a One?: LeetCode 1428. Leftmost Column with at Least a One is rated Medium on LeetCode.
What is the time complexity of LeetCode 1428. Leftmost Column with at Least a One?: The Python solution on this page runs in O(m \times \log n), where m and n are the number of rows and columns of the matrix, respectively.
What is the space complexity of LeetCode 1428. Leftmost Column with at Least a One?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1428. Leftmost Column with at Least a One cover?: LeetCode 1428. Leftmost Column with at Least a One is tagged Array, Binary Search, Interactive and Matrix on LeetCode.
Is LeetCode 1428. Leftmost Column with at Least a One a premium problem?: Yes. LeetCode 1428. Leftmost Column with at Least a One is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.