Practice/Meta/Leetcode 74. Search a 2D Matrix

Leetcode 74. Search a 2D Matrix

CodingMust

Problem

You are given an m x n integer matrix with the following special properties:

• Each row is sorted in ascending order from left to right
• The first integer of each row is strictly greater than the last integer of the previous row

This means if you were to "flatten" the entire matrix into a single array by concatenating all rows, you would get one long sorted array.

Write a function that determines whether a given target value exists anywhere in this matrix. Your solution should take advantage of the sorted structure to achieve better than linear time complexity.

Requirements

1. Return true if the target exists in the matrix, false otherwise
2. Optimize for time complexity by exploiting the sorted property
3. Handle edge cases including empty matrices, single elements, and single rows/columns

Constraints

• m == matrix.length (number of rows)
• n == matrix[i].length (number of columns)
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4
• Each row is sorted in non-decreasing order
• The first element of each row is greater than the last element of the previous row (if it exists)
• Time complexity should be O(log(m × n))
• Space complexity should be O(1)

Examples

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true Explanation: The value 3 is located in the first row at index 1

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false Explanation: The value 13 does not exist in the matrix. It would fall between 11 and 16 if it were present

Example 3:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 60 Output: true Explanation: The value 60 is at the last position of the matrix