Katkat
Back

Find Earliest Column With One

UberSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to optimize searches in a sorted binary matrix by minimizing expensive API calls through efficient traversal techniques.

Problem Statement

You are given a binary matrix of size m x n (m rows, n columns) where each row is sorted in non-decreasing order (i.e., all 0s appear before all 1s). You do not have direct access to the matrix; instead, you must use a provided API method:

int get(int row, int col)

  • Returns 1 if matrix[row][col] is 1, and 0 otherwise.
  • Each call to get is expensive, so you should aim to minimize the number of calls.

Your task is to find the index of the first (leftmost) column that contains at least one 1. If no such column exists (the entire matrix is 0s), return -1.

Function Signature

def find_earliest_column(m: int, n: int) -> int:
    # m: number of rows
    # n: number of columns
    pass

Constraints

  • 1 <= m, n <= 10^5
  • The matrix is implicit; you only have the get(r, c) API.

Examples

Example 1: Input: m = 3, n = 4 Matrix:

0 0 1 1
0 0 0 1
0 1 1 1

Output: 1 Explanation: Column 1 is the first column containing a 1 (in row 2).

Example 2: Input: m = 2, n = 3 Matrix:

0 0 0
0 0 0

Output: -1

Edge Cases

  • Matrix with all 0s.
  • Matrix with all 1s.
  • Single row or single column matrices.

Hints

Hint 1

Since each row is sorted, can you determine the first occurrence of a 1 in a specific row efficiently?

Hint 2

If you know the first column index that contains a 1 for row `i`, how can you use that information to prune your search for row `i+1`?

Hint 3

Consider iterating through the rows while maintaining a variable that tracks the current 'best' column index found so far.

Follow-up questions

  • What is the time complexity of your approach in terms of m and n?
  • How would you modify your algorithm if the matrix were sorted by columns instead of rows?
  • If you were told that the matrix is extremely sparse (mostly 0s), would your approach still be optimal?