How should I practice Search a Row-Major Sorted Matrix?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon onsite interview problems in FastPrep.

Is Search a Row-Major Sorted Matrix associated with Amazon?

FastPrep tags this as a Amazon onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Binary Search

Search a Row-Major Sorted Matrix

Learn this problem

● Medium

AmazonNEW GRADONSITE INTERVIEW

See Amazon hiring insights

Problem statement

Given an integer matrix matrix and an integer target, return true when target appears in the matrix and false otherwise.

Each row is sorted in strictly increasing order. The first value of every row after the first is greater than the final value of the previous row.

Use a binary-search solution with logarithmic running time in the total number of cells.

Function

searchMatrix(matrix: int[][], target: int) → boolean

Examples

Example 1

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]target = 3return = true

The value 3 is the second cell of the first row.

Example 2

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]target = 13return = false

Binary search ends between 11 and 16, so 13 is absent.

Example 3

matrix = []target = 1return = false

An empty matrix contains no target.

Constraints

0 <= matrix.length <= 100.
When matrix is non-empty, 1 <= matrix[i].length <= 100 and every row has the same length.
-10^9 <= matrix[i][j], target <= 10^9.
Rows satisfy the stated global ordering.