37. Search an Element in a Row-Wise and Column-Wise Sorted Matrix

Given an r x c matrix where each row is sorted ascending and the first element of every row is greater than the last element of the previous row, and a target value, print 'Yes' if the target exists in the matrix, otherwise 'No'.

Input: The first line contains r and c, the matrix dimensions. The next r lines each contain c space-separated integers, sorted so the whole matrix reads like one contiguous sorted sequence. The final line contains the target value. Output: Print 'Yes' if the target exists in the matrix, otherwise print 'No'.

1 <= r, c <= 1000

The index-conversion formula (row = index / columns, column = index % columns) is the one small but essential trick that lets a standard 1D binary search work directly on 2D matrix data.

Given a matrix that reads like one giant sorted list when laid end to end, check if a specific value exists in it. Brute force: Scan every single cell of the matrix directly, checking against the target - this costs O(r * c), correct but doesn't leverage the fact that the whole matrix is really just one giant sorted list in disguise. Optimised: Since the matrix behaves EXACTLY like one continuous sorted array (given the specific ordering guarantee in this problem's statement), a standard binary search - just with a small index-conversion step to map a single conceptual index back to a (row, column) pair - finds the target in logarithmic time, just like searching any normal sorted array.

Because every row is sorted ascending and every row's first element exceeds the previous row's last element, the matrix is really one sorted sequence laid out in row-major order. Run a single binary search over the conceptual index range [0, r*c - 1], converting a candidate index mid into its actual row (mid / c) and column (mid % c) to fetch the value for comparison, narrowing the range exactly like an ordinary sorted-array binary search. This finds the target, or proves its absence, in time logarithmic in the total element count, without ever restarting a search per row. Time: O(log(r*c)) Space: O(1)

Since every individual row is sorted ascending, binary search each row independently for the target: if any row's binary search finds it, print 'Yes' immediately, and if all r rows are searched without success, print 'No'. This improves on a pure scan since each row lookup is logarithmic, though it still restarts a fresh search once per row. Time: O(r log c) Space: O(1)

Iterate over every cell of the matrix in any order and compare it to the target, printing 'Yes' the moment a match is found, or 'No' if the scan completes without one. This ignores all sorted structure of the matrix and checks every cell in the worst case. Time: O(r*c) Space: O(1)

1. Recognize that because each row is sorted AND every row's first element is bigger than the previous row's last element, the entire matrix reads as one continuous sorted sequence if you read it row by row. 2. Apply a standard binary search over a CONCEPTUAL single index range from 0 to (rows*columns - 1). 3. Convert any conceptual single index back into an actual (row, column) position using division and modulo by the number of columns. 4. Continue the binary search as normal, comparing the value at the converted position against the target.

Time: O(log(r * c)) - genuine binary search over the conceptual combined size of the whole matrix. Space: O(1) - no extra storage needed beyond a few index variables.

r = 1 or c = 1 (the matrix degenerates to a single sorted line); a target smaller than the first element or larger than the last (print 'No'); and r = c = 1000 (largest, confirming the flattened binary-search approach is O(log(r*c))).

Be careful to distinguish this problem's specific guarantee (the whole matrix reads as ONE sorted sequence) from the WEAKER guarantee in 'Search an Element in a Row-Wise and Column-Wise Sorted Matrix' variants where only rows and columns are individually sorted but rows don't necessarily follow each other in order - the two variants need genuinely different algorithms (binary search here, versus a staircase-search approach for the weaker guarantee).