Baseline Binary Search · 2D Arrays O(m + n) · O(1)
A corrosion map stores thickness readings that increase left to right along every row and top to bottom down every column - but rows do not continue each other, so the grid is not one flat sorted list. An inspector standing at the top-right corner can eliminate a whole row or column with every reading. Confirm whether a target thickness exists on the map.
Input: An m x n matrix where integers increase along each row and down each column, plus an integer target.
Output: true when target appears in the matrix, otherwise false.
1 <= m, n <= 200-10^9 <= matrix[i][j], target <= 10^9Rows and columns are each sorted in ascending orderInput: {"matrix":[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],"target":5}
Output: true
The corner sweep discards columns and rows in turn until it steps onto 5.
Input: {"matrix":[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],"target":20}
Output: false
Every elimination step is justified, and the sweep leaves the map without ever meeting 20.