This problem requires treating the 2D matrix as a virtual sorted array and applying binary search on indices. By mapping each mid-point index back to row and column positions, we can efficiently check values while reducing time complexity. This avoids scanning rows linearly and ensures O(log(m * n)) performance, handling empty rows and boundary conditions carefully to prevent miscalculations.
Problem Statement
You are given an m x n integer matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row. Given an integer target, you must determine whether the target exists in the matrix. The solution must leverage the matrix's sorted structure to minimize unnecessary comparisons and avoid linear scans.
Return true if the target exists in the matrix or false otherwise. You are required to implement an approach that treats the 2D matrix as a flattened sorted array, performing binary search over indices while correctly translating them to row and column coordinates. The algorithm must maintain O(log(m * n)) time complexity and handle edge cases such as the smallest or largest elements.
Examples
Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example details omitted.
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Example details omitted.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
Solution Approach
Flatten Matrix and Apply Binary Search
Conceptually treat the 2D matrix as a 1D array of length m * n, where each index maps to a row and column via row = index / n and col = index % n. Initialize left and right pointers at 0 and m * n - 1, and iteratively check the middle index. If the value equals the target, return true; otherwise, adjust left or right depending on the comparison. This approach ensures all comparisons use the sorted property and never revisits elements unnecessarily.
Edge Handling and Boundary Mapping
Pay careful attention when computing the middle index and translating it back to matrix coordinates to avoid off-by-one errors. Since each row is individually sorted and the first element of each row is larger than the previous row's last, the mapping ensures correct access to values. Handle cases where the target is smaller than the first element or larger than the last element to exit early, preventing redundant search iterations and maintaining consistent O(log(m * n)) performance.
Avoid Linear Search in Rows
Do not scan rows linearly even if the target might be close to a row boundary; doing so violates the required logarithmic complexity. Instead, rely entirely on the virtual 1D index binary search to navigate the matrix. This ensures that every decision halves the search space. Additionally, avoid common mistakes such as using mid incorrectly or assuming the matrix is rectangular without validating the number of columns. Correctly managing the virtual flattening preserves efficiency and prevents subtle off-by-one failures.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
The binary search over the flattened matrix ensures a time complexity of O(log(m * n)) because each iteration halves the search space. Space complexity remains O(1) as only pointers and a few integer variables are used for mapping indices to rows and columns, with no additional arrays or recursion overhead.
What Interviewers Usually Probe
- Do you understand how to map a 1D index back to 2D coordinates in the matrix?
- Can you adjust your binary search if the target is smaller than the first element or larger than the last?
- Will you maintain O(log(m * n)) complexity without scanning any row linearly?
Common Pitfalls or Variants
Common pitfalls
- Miscomputing row and column from a 1D index leading to wrong value comparisons.
- Attempting linear search in individual rows which breaks the logarithmic time requirement.
- Incorrect handling of edge targets that match the first or last element of the matrix, causing off-by-one errors.
Follow-up variants
- Search a 2D matrix II where rows and columns are independently sorted but not fully flattened.
- Search a rotated 2D matrix with unknown rotation point while preserving sorted property in rows.
- Find the k-th smallest element in a sorted 2D matrix using a similar binary search over value space.
How GhostInterview Helps
- Capture the matrix and target input directly from the screen for immediate testing and verification.
- Provide step-by-step binary search solution path with mapped indices and complexity explanation to guide decisions.
- Support screen-share workflows allowing code and matrix visualization layers to ensure correct index mapping and debugging.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How does binary search apply to Search a 2D Matrix?
Binary search treats the 2D matrix as a virtual flattened array, allowing logarithmic search by mapping indices to rows and columns instead of scanning linearly.
What happens if the target is the first or last element?
The algorithm correctly identifies targets at matrix boundaries by computing the mid-point mapping and avoids off-by-one errors during index translation.
Can this approach handle non-rectangular matrices?
The standard solution assumes all rows have equal columns; non-rectangular matrices require additional checks or adjusted index mapping to preserve correctness.
Why is linear row search incorrect here?
Linear row scanning violates the O(log(m * n)) requirement and misses the optimization gained from binary search over the fully flattened matrix index space.
What is the key failure mode in this problem?
A common failure mode is miscalculating row and column from the 1D index, which causes false negatives or incorrect comparisons during binary search iterations.
Need direct help with Search a 2D Matrix instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Search a 2D Matrix from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Efficiently search for a target in a 2D matrix using binary search and matrix properties.
Open problem page#363 Max Sum of Rectangle No Larger Than KSolve the "Max Sum of Rectangle No Larger Than K" problem using binary search over the valid sum space to optimize space and time complexity.
Open problem page#378 Kth Smallest Element in a Sorted MatrixFind the kth smallest element in a sorted n x n matrix using efficient binary search or heap strategies for optimized memory usage.
Open problem page