Understanding the Problem
We are given a 2D matrix where each row and each column is sorted in non-decreasing order. Our goal is to determine whether a specific target value exists in the matrix.
This isn't just any matrix—its sorted nature gives us a big advantage. We don't have to search every cell. Instead, we can intelligently move through the matrix to find the target faster.
Step-by-Step Solution with Example
Step 1: Choose a Starting Point
We begin at the top-right corner of the matrix. Let’s say our matrix is:
int[][] matrix = {
{1, 4, 7, 11},
{2, 5, 8, 12},
{3, 6, 9, 16},
{10,13,14,17}
};
int target = 5;
The element at the top-right is 11
. This choice is strategic because it allows us to eliminate either a row or a column based on the comparison with the target.
Step 2: Compare and Move
Compare the current element (starting at matrix[0][3] = 11
) with the target:
- If current element equals target → we found it!
- If current element greater than target → move left (since elements to the left are smaller)
- If current element less than target → move down (since elements below are larger)
Step 3: Walk Through the Example
- Start at
matrix[0][3] = 11
. 11 > 5 → move left
- Now at
matrix[0][2] = 7
. 7 > 5 → move left
- Now at
matrix[0][1] = 4
. 4 < 5 → move down
- Now at
matrix[1][1] = 5
. Match found!
We found the target in just 4 steps, without checking all 16 elements!
Step 4: Implement the Logic
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
if (rows == 0) return false;
int cols = matrix[0].length;
int row = 0, col = cols - 1;
while (row < rows && col >= 0) {
if (matrix[row][col] == target) return true;
else if (matrix[row][col] > target) col--;
else row++;
}
return false;
}
Edge Cases
- Empty Matrix: If the matrix is empty or has zero columns, return
false
immediately.
- Single Element: If the matrix has one element, compare it directly with the target.
- Target smaller than all elements: We’ll keep moving left and go out of bounds quickly.
- Target greater than all elements: We’ll move down and exit the matrix without finding it.
- Negative values or duplicates: Still handled correctly, as the sorted structure remains valid.
Finally
This method takes advantage of the matrix's sorted properties. By starting at the top-right, we are always moving closer to our goal and never backtracking. This makes the solution both intuitive and efficient.
The time complexity is O(N + M)
, where N is the number of rows and M is the number of columns. This is far better than a brute-force O(N * M)
search.
For beginners, it’s a great example of how understanding data structure properties helps in writing optimized code.
Comments
Loading comments...