{x}
blog image

Leftmost Column with at Least a One

Solution Explanation: Finding the Leftmost Column with at Least a One

This problem involves finding the index of the leftmost column in a row-sorted binary matrix that contains at least one '1'. The challenge is that you can't directly access the matrix; you must use a BinaryMatrix interface with get(row, col) and dimensions() methods. The solution uses a binary search approach for optimal efficiency.

Approach:

  1. Get Dimensions: First, retrieve the matrix dimensions (rows and columns) using binaryMatrix.dimensions().

  2. Iterate Through Rows: Iterate through each row of the matrix.

  3. Binary Search in Each Row: For each row, perform a binary search to find the index of the leftmost '1'. Binary search is ideal here because the rows are sorted.

  4. Track Minimum Index: Keep track of the minimum index (leftmost column) found across all rows.

  5. Handle No Ones: If no '1' is found in any row, return -1. Otherwise, return the minimum index.

Time Complexity: O(M * log N), where M is the number of rows and N is the number of columns. The outer loop iterates M times, and the binary search in each row takes O(log N) time.

Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (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[]:
 
import bisect
 
class Solution:
    def leftMostColumnWithOne(self, binaryMatrix: "BinaryMatrix") -> int:
        rows, cols = binaryMatrix.dimensions()
        leftmost_one = cols  # Initialize with a value larger than any possible index
 
        for row in range(rows):
            #Use bisect_left for efficient search of the leftmost 1
            index = bisect_left(range(cols), 1, key=lambda col: binaryMatrix.get(row, col))
            #Update the leftmost_one only if a 1 is found in the current row and it's to the left of the current leftmost_one
            if index < cols and index < leftmost_one :
                leftmost_one = index
 
 
        return leftmost_one if leftmost_one < cols else -1

Code Implementation (Java):

/**
 * // 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> dims = binaryMatrix.dimensions();
        int rows = dims.get(0);
        int cols = dims.get(1);
        int leftmostOne = cols;
 
        for (int i = 0; i < rows; i++) {
            int left = 0;
            int right = cols -1;
            int index = -1; // Initialize index to -1
 
            while(left <= right){
                int mid = left + (right - left)/2;
                if(binaryMatrix.get(i, mid) == 1){
                    index = mid; //Found a 1, update index
                    right = mid -1; //Search in the left half to find the leftmost 1
                } else {
                    left = mid + 1; // Search in the right half
                }
            }
            if(index != -1 && index < leftmostOne){
                leftmostOne = index;
            }
 
        }
 
        return leftmostOne == cols ? -1 : leftmostOne;
    }
}

Other Languages: The same approach can be implemented effectively in other languages like C++, Go, JavaScript, TypeScript, and C# using their respective binary search mechanisms (e.g., lower_bound in C++, sort.Search in Go). The core logic remains consistent across all implementations.