Search a 2D Matrix
Write an efficient algorithm that searches for a value in an $m \times n$ matrix. The matrix has sorted rows and the first integer of each row is greater than the last of the previous row. Use two Binary Searches.
Why Interviewers Ask This
IBM interviewers ask this question to evaluate a candidate's ability to recognize hidden data structures within complex constraints. They specifically test if you can transform a 2D problem into a 1D search space using mathematical mapping rather than brute force. This assesses your optimization mindset, understanding of logarithmic time complexity, and capacity to handle edge cases in sorted arrays.
How to Answer This Question
1. Clarify the Constraints: Immediately confirm that rows are sorted left-to-right and each row starts with a value greater than the previous row's end. This unique property is the key to the solution.
2. Propose the Strategy: Explicitly state you will use two binary searches. Explain that the first identifies the correct row, and the second finds the target within that row.
3. Define Row Search Logic: Describe how to compare the target against the first and last element of mid-rows to determine which row contains the potential match.
4. Define Column Search Logic: Once the row is identified, explain running a standard binary search on that specific row's indices.
5. Analyze Complexity: Conclude by stating the time complexity is O(log m + log n) and space complexity is O(1), demonstrating awareness of efficiency standards expected at IBM.
Key Points to Cover
- Recognizing the matrix can be mathematically mapped to a 1D sorted array
- Explicitly proposing two separate binary search operations
- Demonstrating O(log m + log n) time complexity analysis
- Maintaining O(1) auxiliary space complexity
- Handling edge cases like empty matrices or single-row inputs
Sample Answer
To solve this efficiently, I would leverage the matrix's unique sorting property where every row starts after the previous one ends. This allows us to treat the entire 2D grid as a single sorted 1D array of size m times n. However, since we cannot physically flatten it without extra space, I will implement two distinct binary searches to maintain O(1) space complexity.
First, I will perform a binary search across the rows. For any middle row, I check if the target falls between its first and last element. If it does, I've found our candidate row. If the target is smaller than the first element of the middle row, I search the upper half; otherwise, I search the lower half.
Once the correct row index is isolated, I execute a second binary search strictly within that row to locate the exact column index of the target value. If the inner search fails, the value is not present.
This approach ensures we eliminate half the search space with each step, resulting in a time complexity of O(log m + log n). This is significantly better than the O(m*n) brute-force approach or even O(m log n) approaches that only optimize the column search. Given IBM's focus on scalable systems, this logarithmic efficiency is critical for handling large datasets without memory overhead.
Common Mistakes to Avoid
- Attempting to flatten the matrix into a new array, which violates the O(1) space constraint
- Using nested loops (O(m*n)) instead of binary search due to overlooking the sorted property
- Confusing the row search logic by comparing against random elements instead of row boundaries
- Failing to verify if the target exists before attempting the second binary search
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.