Description
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Examples:
Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true
Example 2:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: falseSolution in Python
Approach:
- Matrix Properties:
- Each row is sorted from left to right.
- Each column is sorted from top to bottom.
- Optimal Approach:
- Start from the top-right corner of the matrix.
- If the current element is greater than the target, move left (to reduce the value).
- If the current element is less than the target, move down (to increase the value).
- This allows us to efficiently eliminate either an entire row or column in each step.
- Time Complexity:
- Since we traverse either left or down in each step, the algorithm runs in O(m + n) time, where
mis the number of rows andnis the number of columns.
- Since we traverse either left or down in each step, the algorithm runs in O(m + n) time, where
Python
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# Step 1: Get the dimensions of the matrix
if not matrix or not matrix[0]:
return False # Handle edge case of empty matrix
rows = len(matrix) # Number of rows in the matrix
cols = len(matrix[0]) # Number of columns in the matrix
# Step 2: Start at the top-right corner of the matrix
row = 0 # Row pointer starts at the first row
col = cols - 1 # Column pointer starts at the last column
# Step 3: Iterate while row and col are within bounds
while row < rows and col >= 0:
current_value = matrix[row][col]
# Step 4: Compare current value with the target
if current_value == target:
return True # Target found
# Step 5: If current value is greater than the target, move left
elif current_value > target:
col -= 1 # Move to the left column
# Step 6: If current value is less than the target, move down
else:
row += 1 # Move to the next row
# Step 7: If we exit the loop, target is not found
return FalseExplanation of Each Step:
- Matrix and Edge Case:
- First, we check if the matrix or the first row is empty. If so, we return
Falsebecause there’s nothing to search.
- First, we check if the matrix or the first row is empty. If so, we return
- Initialize Pointers:
- We start from the top-right corner (
matrix[0][cols - 1]), which is the largest element in the first row and the smallest element in the last column.
- We start from the top-right corner (
- Traverse the Matrix:
- If the current element is equal to the target, we return
True. - If the current element is larger than the target, it means we need a smaller value, so we move left (decrement the column).
- If the current element is smaller than the target, we need a larger value, so we move down (increment the row).
- If the current element is equal to the target, we return
- Return
False:- If we exhaust the matrix without finding the target, return
False.
- If we exhaust the matrix without finding the target, return
Solution in C++
C++
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// Step 1: Check if the matrix is empty or has no columns
if (matrix.empty() || matrix[0].empty()) {
return false; // Handle the edge case where the matrix is empty
}
// Step 2: Get the number of rows and columns
int rows = matrix.size(); // Number of rows in the matrix
int cols = matrix[0].size(); // Number of columns in the matrix
// Step 3: Initialize row and column pointers
int row = 0; // Start at the first row
int col = cols - 1; // Start at the last column (top-right corner)
// Step 4: Traverse the matrix while within bounds
while (row < rows && col >= 0) {
int current_value = matrix[row][col]; // Current element
// Step 5: If the current value is the target, return true
if (current_value == target) {
return true; // Target found
}
// Step 6: If the current value is greater than the target, move left
else if (current_value > target) {
col--; // Move left to reduce the value
}
// Step 7: If the current value is less than the target, move down
else {
row++; // Move down to increase the value
}
}
// Step 8: If we finish the loop without finding the target, return false
return false; // Target not found
}
};Solution in Javascript
JavaScript
var searchMatrix = function(matrix, target) {
// Step 1: Check if matrix is empty or has no columns
if (matrix.length === 0 || matrix[0].length === 0) {
return false; // Return false if matrix is empty
}
// Step 2: Initialize variables to track the current position
let rows = matrix.length; // Number of rows in the matrix
let cols = matrix[0].length; // Number of columns in the matrix
let row = 0; // Start at the first row
let col = cols - 1; // Start at the last column (top-right corner)
// Step 3: Traverse the matrix while within bounds
while (row < rows && col >= 0) {
let currentVal = matrix[row][col]; // Get the current value
// Step 4: Check if the current value matches the target
if (currentVal === target) {
return true; // Target found
}
// Step 5: If current value is greater than the target, move left
if (currentVal > target) {
col--; // Move left to reduce the value
}
// Step 6: If current value is less than the target, move down
else {
row++; // Move down to increase the value
}
}
// Step 7: If the loop completes without finding the target, return false
return false; // Target not found
};Solution in Java
Java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// Step 1: Check if the matrix is empty or has no columns
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false; // Return false if matrix is empty or invalid
}
// Step 2: Initialize rows and columns for traversal
int rows = matrix.length; // Number of rows in the matrix
int cols = matrix[0].length; // Number of columns in the matrix
// Step 3: Start from the top-right corner of the matrix
int row = 0; // Start at the first row
int col = cols - 1; // Start at the last column (top-right corner)
// Step 4: Traverse the matrix while staying within the bounds
while (row < rows && col >= 0) {
// Get the current value in the matrix
int currentValue = matrix[row][col];
// Step 5: Check if the current value matches the target
if (currentValue == target) {
return true; // Target found, return true
}
// Step 6: If the current value is greater than the target, move left
if (currentValue > target) {
col--; // Move left to reduce the value
}
// Step 7: If the current value is less than the target, move down
else {
row++; // Move down to increase the value
}
}
// Step 8: If we exit the loop without finding the target, return false
return false; // Target not found
}
}