65. Search a Row-major Sorted Matrix
The values are sorted when rows are read from left to right, top to bottom. Determine whether the target exists without copying all matrix cells into a separate array.
This ordering is stronger than independently sorted rows. Treat empty shapes and shape validation according to the contract below.
Example 1
Input
[[1,3,5],[7,9,11]], target=7
Output
true
Explanation: Virtual index 3 maps to row 1, column 0 using division/remainder by three columns.
Example 2
Input
[[1,3,5],[7,9,11]], target=6
Output
false
Explanation: The value lies between rows but need not exist at the insertion boundary.
Example 3
Input
[[],[]], any target
Output
false
Explanation: A valid zero-column rectangle has no indexable cell.
Constraints
0 <= matrix.length, matrix[r].length <= 105-231 <= matrix[r][c] <= 231 - 1-231 <= target <= 231 - 1- Rows have equal length; the row-major sequence is nondecreasing.
Hints
Hint 1
Imagine one globally sorted array, but avoid actually building it.
Hint 2
How does a virtual index map to row and column when every row has C cells?
Hint 3
Use a long [0,R*C) interval and map mid via /C and %C; guard empty dimensions first.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Virtual index maps across a row boundary
[[1,3,5],[7,9,11]]
7
true