MEDIUM NC#29 Binary Search
74. Search a 2D Matrix
📖 Problem
You are given an m x 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.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •Midpoint overflow-safe math
- •Loop invariants
- •Monotonic condition design
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply Binary Search reasoning pattern
💡 Approach
- → Treat 2D matrix as flattened 1D array
- → Use binary search on virtual 1D array
- → Map mid index to row and column: row = mid // n, col = mid % n
- → Time: O(log(m*n)), Space: O(1)
- → pass binary search O(log m + log n), Linear scan O(m*n)
🧭 Prerequisites
🛠️ Hints & Pitfalls
Hints
- •Treat 2D matrix as flattened 1D array
- •Use binary search on virtual 1D array
- •Map mid index to row and column: row = mid // n, col = mid % n
Common Pitfalls
- •Time: O(log(m*n)), Space: O(1)
- •pass binary search O(log m + log n), Linear scan O(m*n)
🧪 Test Cases
Hidden tests on submit: 2
Test Case 1
Not run Input:
searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3); Expected:
true Test Case 2
Not run Input:
searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13); Expected:
false Test Case 3
Not run Input:
searchMatrix([[1]], 1); Expected:
true 📝 Code Editor
📤 Output