MediumBinary SearchAI interview only
Search a 2D Matrix
Asked atgoogleamazonmetamicrosoftapplebloomberg
01 · Problem
You are given an m x n integer matrix matrix with the following two properties:
- Each row is sorted in non-decreasing order.
- The first integer of each row is greater than the last integer of the previous row.
Given an integer target, return true if target is in matrix or false otherwise.
You must write a solution in O(log(m * n)) time complexity.
02 · Examples
Example 01
Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output
true
3 is found in the matrix at row 0, column 1.
Example 02
Input
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output
false
13 is not present in the matrix.
Example 03
Input
matrix = [[1]], target = 1
Output
true
The matrix has a single element which equals the target.
03 · Constraints
- 01m == matrix.length
- 02n == matrix[i].length
- 031 <= m, n <= 100
- 04-104 <= matrix[i][j], target <= 104
04 · Optimal complexity
- Time
- O(log(m * n))
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.