Loading problem…
You are given an m x n integer 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.
Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: Reading the rows one after another gives one sorted list: 1, 3, 5, 7, 10, … 3 is in it (row 0, column 1).
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: 13 would fall between 11 and 16 in row 1, but it is not there.
Example 3
Input: matrix = [[1]], target = 1
Output: true
Explanation: The only cell holds 1, which is the target.
Because each row's first element exceeds the previous row's last, the whole matrix reads as one sorted sequence. Binary search over the virtual index range [0, m*n) and map each mid index back to a (row, col) with divide and modulo.
Run checks all cases above. Submit evaluates all test cases.