Search a 2D Matrix in LogN

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Search a 2D Matrix in LogN. Start with the requirements on the right.

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

You need to log in / sign up to run or submit.

Problem

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 solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output