Search a 2D Matrix
Problem link: https://leetcode.com/problems/search-a-2d-matrix/
Problem Statement
You are given an m x n integer matrix matrix with the following two properties:
- Each row is sorted in non-decreasing order.
- 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.
Input
An m x n matrix and an integer target.
Output
Boolean (true if target exists, false otherwise).
Example
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true
Explanation
The values flow continuously: 7 is followed by 10, 20 is followed by 23. This allows us to treat the grid as a single sorted list: [1, 3, 5, 7, 10, 11, 16, 20, 23, 30, 34, 60].
Brute Force
Intuition
Perform a linear scan through every row and every column until the target is found or the end of the matrix is reached.
Approach
- Loop through each row from i = 0 to m-1.
- Loop through each column from j = 0 to n-1.
- If matrix[i][j] == target, return true.
- If loops finish, return false.
Dry Run
matrix = [[1, 3]], target = 3 Check (0,0): 1 != 3 Check (0,1): 3 == 3. Found!
Code (Java)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == target) return true;
}
}
return false;
}
}
Complexity Analysis
In the worst case, we visit every single element in the matrix.
Optimal Solution
Intuition
Since the matrix is fully sorted, we treat it as a virtual 1D array. A 1D index idx can be converted to 2D coordinates using: row = idx / n and col = idx % n (where n is the number of columns). We then apply standard Binary Search.
Approach
- Initialize low = 0 and high = (m * n) - 1.
- While low <= high:
- Find mid = low + (high - low) / 2.
- Get matrix value:
val = matrix[mid / n][mid % n]. - If val == target, return true.
- If val < target, low = mid + 1.
- Else, high = mid - 1.
- Return false if not found.
Dry Run
matrix [3x4], target = 3 low=0, high=11 mid=5 -> row=1, col=1 -> matrix[1][1] = 11 11 > 3, so high=4 mid=2 -> row=0, col=2 -> matrix[0][2] = 5 5 > 3, so high=1 mid=0 -> row=0, col=0 -> matrix[0][0] = 1 1 < 3, so low=1 mid=1 -> row=0, col=1 -> matrix[0][1] = 3. Found!
Code (Java)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) return false;
int m = matrix.length;
int n = matrix[0].length;
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int midVal = matrix[mid / n][mid % n];
if (midVal == target) return true;
else if (midVal < target) low = mid + 1;
else high = mid - 1;
}
return false;
}
}
Complexity Analysis
Binary search divides the search space in half each time across M*N total elements.
Quick Revision (Brute Force)
- Linear scan (M*N)
- O(M*N) time
Quick Revision (Optimal)
- Virtual 1D Binary Search
- row = mid / n, col = mid % n
- O(log(M*N)) time
- O(1) space