We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Leftmost Column with at Least a One

Number: 1374

Difficulty: Medium

Paid? Yes

Companies: Uber, Meta

Problem Description

Given a row-sorted binary matrix where each row is sorted in non-decreasing order (i.e., all 0s come before 1s), find the leftmost column index that contains at least one 1. If no such column exists, return -1. The matrix can only be accessed through the provided BinaryMatrix interface with two functions: get(row, col) and dimensions().

Key Insights

  • Each row is sorted, meaning once a 1 is encountered in a row, all elements to its right are also 1.
  • Instead of performing a binary search on every row independently, one can optimize by starting from the top-right corner.
  • From the top-right corner, if you encounter a 1, move left; if you encounter a 0, move down.
  • This approach takes advantage of the matrix's sorted nature, ensuring no unnecessary checks and limiting the number of get calls.

Space and Time Complexity

Time Complexity: O(rows + cols) Space Complexity: O(1)

Solution

We use a two-pointer approach starting from the top-right corner of the matrix. The idea is to keep track of the current position using two indices: one for the row (starting at 0) and one for the column (starting at cols - 1). If the current element is 1, we update the result to the current column index and move left. Otherwise, if it’s 0, we move down. This process continues until we move out of bounds, ensuring we efficiently find the leftmost column with a 1.

Code Solutions

# Python solution with detailed comments
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix):
        # Retrieve the dimensions of the matrix (rows, cols)
        rows, cols = binaryMatrix.dimensions()
        # Initialize the starting position at the top-right corner
        current_row = 0
        current_col = cols - 1
        # This will hold the leftmost column index containing a 1
        result = -1
        # Iterate through the matrix while within valid boundaries
        while current_row < rows and current_col >= 0:
            # If we find a 1, update the result and move left to check for earlier ones
            if binaryMatrix.get(current_row, current_col) == 1:
                result = current_col
                current_col -= 1
            # If the element is 0, move down to the next row
            else:
                current_row += 1
        return result
← Back to All Questions