Search a 2D Matrix in LogN | Dataford Interview Questions

FourKites can represent shipment records in a matrix ordered by increasing tracking priority. Each row is sorted in nondecreasing order, and the first value in every row is greater than the last value in the previous row. Implement search_2d_matrix(matrix, target) to determine whether target exists.

Your algorithm must run in O(log(m × n)) time, where m is the number of rows and n is the number of columns. Treat the matrix as one sorted array without creating a flattened copy.

Formal Specification

Input: matrix, a rectangular list of lists containing integers, and target, an integer.
Output: Return True if target appears in the matrix; otherwise return False.
An empty matrix is valid and should return False.

Constraints

0 <= m <= 1000
If m > 0, 1 <= n <= 1000
-10^9 <= matrix[i][j], target <= 10^9
Every row has exactly n elements
The first value of each row is greater than the last value of the previous row

Function Signature

def search_2d_matrix(matrix, target):

Your question is Search a 2D Matrix in LogN. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem