Introduction

If each row of a matrix is sorted in non-decreasing order, the smallest value in any given row is its first element. That means finding the row containing the smallest integer in the whole matrix is much easier than scanning every cell: compare the first element of each row and keep the best row index.

Why the First Column Is Enough

Suppose the matrix is row-wise sorted:

1[
2  [4, 8, 9],
3  [1, 5, 7],
4  [3, 6, 10]
5]

Because each row is sorted left to right, the row minimums are:

• row 0: 4
• row 1: 1
• row 2: 3

The global smallest value must therefore be among those first-column entries. There is no need to inspect the rest of any row.

A Simple O(m) Algorithm

If the matrix has m rows, scan the first element of each row once.

1def row_with_smallest_value(matrix):
2    if not matrix or not matrix[0]:
3        raise ValueError("matrix must be non-empty")
4
5    min_row = 0
6    min_value = matrix[0][0]
7
8    for row_index in range(1, len(matrix)):
9        if matrix[row_index][0] < min_value:
10            min_value = matrix[row_index][0]
11            min_row = row_index
12
13    return min_row, min_value
14
15
16matrix = [
17    [4, 8, 9],
18    [1, 5, 7],
19    [3, 6, 10],
20]
21
22print(row_with_smallest_value(matrix))  # (1, 1)

This runs in O(m) time and uses O(1) extra space.

Why You Do Not Need Binary Search

Because each row is sorted, people often look for a binary-search trick. In this specific problem, binary search does not help much because the answer is fully determined by the first element of each row.

Binary search becomes relevant for different matrix problems, such as:

• searching for a target value
• finding the first positive value in each row
• counting elements below a threshold

But for "which row contains the smallest integer," the first column already gives everything you need.

Handling Edge Cases

Real code should decide how to handle:

• an empty matrix
• empty rows
• ties where multiple rows have the same smallest value

For example, the implementation above returns the first row that achieves the minimum. That is a reasonable default, but you could also return all matching rows if the application needs that.

Here is a variation that returns every row tied for the minimum:

1def rows_with_smallest_value(matrix):
2    if not matrix or not matrix[0]:
3        raise ValueError("matrix must be non-empty")
4
5    min_value = min(row[0] for row in matrix)
6    return [i for i, row in enumerate(matrix) if row[0] == min_value], min_value
7
8
9matrix = [
10    [2, 4, 5],
11    [1, 3, 8],
12    [1, 6, 9],
13]
14
15print(rows_with_smallest_value(matrix))  # ([1, 2], 1)

A Useful Mental Shortcut

The structure of the matrix tells you which cells can possibly matter. Since every row grows left to right, any element after the first column is guaranteed to be greater than or equal to its row's first element.

So the problem reduces from "search an entire matrix" to "scan one value per row." That kind of reduction is a useful habit in algorithm design.

Common Pitfalls

The biggest pitfall is overcomplicating the problem and scanning every element. That works, but it ignores the sorted-row property that makes the problem trivial.

Another common issue is assuming the whole matrix is globally sorted. The problem only says rows are individually sorted, so comparing first elements is valid, but other matrix-wide shortcuts may not be.

People also forget to handle empty input. A matrix function should define whether it raises an exception, returns None, or uses some other convention.

Summary

• In a row-wise sorted matrix, each row's smallest element is its first element.
• The row containing the global minimum can be found by scanning the first column only.
• The resulting algorithm runs in O(number_of_rows) time and O(1) extra space.
• Binary search is unnecessary for this exact problem.
• Decide how your code should handle empty input and ties between rows.