DSA problem
Search a 2D Matrix
You are given an m × n integer matrix matrix with the following two properties: each row is sorted in non-decreasing order, and 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.
The strong property — every row's first element exceeds the previous row's last — means that if you read the matrix in row-major order, you get a single sorted 1D array. So binary search the virtual flat index in [0, m*n - 1] and convert each midpoint back to 2D coordinates with row = idx / n and col = idx % n.
This avoids a two-step search (find row, then find column inside it) and matches the desired O(log(m * n)) bound exactly. The shape is the classic inclusive-bounds binary search: lo = 0, hi = m * n - 1, while lo <= hi, decide whether to move lo or hi based on comparing matrix[idx / n][idx % n] to target.
The pitfall to watch for is that m * n can be large; cast to long or pre-store as long long if the language uses 32-bit ints. For LeetCode's constraints (m * n <= 10^5) this is not a concern, but the habit is worth keeping.
Examples
matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3truematrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13falsematrix = [[1]], target = 1trueConstraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -10^4 <= matrix[i][j], target <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.