Leftmost Column with at Least a One - Practice Coding Problems

Leftmost Column with at Least a One - Problem

You are given a row-sorted binary matrix where all elements are either 0 or 1, and each row is sorted in non-decreasing order.

Your task is to find the leftmost column that contains at least one 1. Return the 0-indexed column number, or -1 if no such column exists.

Important constraints:

You cannot access the matrix directly
You can only use the BinaryMatrix interface with methods:
- get(row, col) - returns the element at position (row, col)
- dimensions() - returns [rows, cols] as a list
Your solution must make at most 1000 calls to BinaryMatrix.get()

Input & Output

Example 1 — Basic Case

$ Input: binaryMatrix = [[0,0],[1,1]]

› Output: 0

💡 Note: The leftmost column with a 1 is column 0. Row 1 has a 1 at position (1,0).

Example 2 — No Ones

$ Input: binaryMatrix = [[0,0],[0,0]]

› Output: -1

💡 Note: There are no 1s in the matrix, so return -1.

Example 3 — Multiple Rows

$ Input: binaryMatrix = [[0,0,1],[0,1,1],[0,0,1]]

› Output: 1

💡 Note: The leftmost column with a 1 is column 1. Row 1 has the first 1 at position (1,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

Visualization

Tap to expand

Understanding the Visualization

Input

Row-sorted binary matrix via BinaryMatrix interface

Process

Find leftmost column with any 1 using minimal API calls

Output

Return column index or -1 if no 1s exist

Key Takeaway

🎯 Key Insight: Use the sorted property to eliminate entire rows/columns with strategic traversal from top-right corner

Asked in

f Facebook 8 G Google 5 a Amazon 3

The key insight is to leverage the sorted property of rows to avoid checking every cell. The optimal approach starts from the top-right corner and moves strategically: left when finding a 1 (to find earlier columns), down when finding a 0 (since no 1s exist to the left in that row). Time: O(m + n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Each Row	O(m × log n)	O(1)	Use binary search to find first 1 in each row, track minimum column
Brute Force - Column by Column	O(m × n)	O(1)	Check each column from left to right until finding one with a 1
Start from Top-Right Corner	O(m + n)	O(1)	Start from top-right, move left when seeing 1, down when seeing 0

Binary Search on Each Row — Algorithm Steps

Get matrix dimensions
For each row, use binary search to find first 1
Track minimum column index
Return minimum column or -1 if no 1s found

Visualization

Tap to expand

Step-by-Step Walkthrough

Row Search

Binary search each row for first 1

Track Minimum

Keep track of leftmost column found

Result

Return minimum column index

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int** matrix;
    int rows;
    int cols;
    int calls;
} BinaryMatrix;

int get(BinaryMatrix* bm, int row, int col) {
    bm->calls++;
    return bm->matrix[row][col];
}

int* dimensions(BinaryMatrix* bm) {
    int* dims = (int*)malloc(2 * sizeof(int));
    dims[0] = bm->rows;
    dims[1] = bm->cols;
    return dims;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(BinaryMatrix* binaryMatrix) {
    int* dims = dimensions(binaryMatrix);
    int rows = dims[0], cols = dims[1];
    free(dims);
    
    int minCol = cols;
    
    for (int row = 0; row < rows; row++) {
        int left = 0, right = cols - 1;
        int firstOne = cols;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (get(binaryMatrix, row, mid) == 1) {
                firstOne = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        minCol = min(minCol, firstOne);
    }
    
    return minCol < cols ? minCol : -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple matrix parsing for demo
    BinaryMatrix bm;
    bm.rows = 2;
    bm.cols = 3;
    bm.calls = 0;
    
    bm.matrix = (int**)malloc(bm.rows * sizeof(int*));
    for (int i = 0; i < bm.rows; i++) {
        bm.matrix[i] = (int*)malloc(bm.cols * sizeof(int));
    }
    
    // Example matrix [[0,0,1],[1,0,1]]
    bm.matrix[0][0] = 0; bm.matrix[0][1] = 0; bm.matrix[0][2] = 1;
    bm.matrix[1][0] = 1; bm.matrix[1][1] = 0; bm.matrix[1][2] = 1;
    
    printf("%d\n", solution(&bm));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × log n)

Binary search on each of m rows takes log n time

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Each Row — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler