
Problem Statement
The task is to develop an algorithm to efficiently search for a specified value, referred to as target
, within a two-dimensional grid or matrix. This matrix is defined by dimensions m x n
, where m
represents the number of rows and n
represents the number of columns. The unique characteristics of this matrix are as follows:
- Each row contains integers arranged in an ascending order from left to right.
- Each column also contains integers arranged in ascending order from top to bottom.
These properties can significantly aid in creating a more efficient search algorithm by leveraging the sorted nature of the matrix's rows and columns.
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:
false
Constraints
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
- All the integers in each row are sorted in ascending order.
- All the integers in each column are sorted in ascending order.
-109 <= target <= 109
Approach and Intuition
To tackle the problem of searching in a matrix with both rows and columns sorted in ascending order, we can utilize a more strategic approach rather than a brute force search. Here, we will explore the intuitive "step-wise" approach:
- Start from a corner of the matrix. The top-right corner is often a good starting point because it allows you to move left if the current value is greater than the target or move down if the current value is less than the target.
- Compare the target with the element at the current position of the matrix:
- If the target is equal to the element, return
true
. - If the target is less than the element, move one column to the left (i.e., decrease the column index).
- If the target is greater than the element, move one row downwards (i.e., increase the row index).
- If the target is equal to the element, return
- Continue this process until you either find the target or exhaust possible moves within the boundaries of the matrix (i.e., you can't move left or down anymore).
- If no matching element is found by the time you exit the loops, return
false
.
This step-wise search is efficient as each move makes a definite elimination of either a row or a column, reducing the search area with each step.
Given the constraints that both m
and n
can be as large as 300, this efficient approach is permissible within these bounds, as each step logically reduces the problem size. Comparatively, employing straightforward linear or binary search techniques row-wise or column-wise may not fully utilize the sorted properties of both the rows and the columns simultaneously as effectively as the described approach.
Solutions
- Java
class Solution {
public boolean matrixSearch(int[][] grid, int key) {
int i = grid.length - 1;
int j = 0;
while (i >= 0 && j < grid[0].length) {
if (grid[i][j] > key) {
i--;
} else if (grid[i][j] < key) {
j++;
} else {
return true;
}
}
return false;
}
}
This solution describes a method to search for a specific value in a 2D matrix which is sorted such that each row's elements and each column's elements are in ascending order. The Java implementation provided involves a function matrixSearch
which utilizes an efficient searching mechanism taking advantage of the matrix's properties.
Strategically start the search from the bottom-left corner of the matrix:
- Initialize two pointers: one (
i
) at the last row, and another (j
) at the first column.
The search process involves the following steps:
- Compare the current element pointed at by
grid[i][j]
to the target valuekey
. - If the current element is greater than the target, move vertically upwards by decrementing
i
to possibly find a smaller element. - If the current element is less than the target, move horizontally right by incrementing
j
to find a larger element. - Repeat the process until either:
- The element is found, in which case
true
is returned. - The search space is exhausted (i.e.,
i
orj
moves out of matrix bounds), andfalse
is returned.
- The element is found, in which case
This method effectively reduces the search space with each comparison, leading to a time complexity better than a brute-force approach. Make sure the matrix adheres to the sorted property for correct function of the algorithm.
- Python
class Solution:
def findInMatrix(self, mtx: List[List[int]], val: int) -> bool:
if not mtx or not mtx[0]:
return False
max_rows = len(mtx)
max_cols = len(mtx[0])
r = max_rows - 1
c = 0
while r >= 0 and c < max_cols:
if mtx[r][c] > val:
r -= 1
elif mtx[r][c] < val:
c += 1
else:
return True
return False
To tackle the problem of searching a value in a 2-dimensional matrix where the matrix is sorted in a row-wise and column-wise manner, the provided Python code employs an efficient search strategy utilizing a two-pointer technique. Here's how the solution operates:
The function first checks if the matrix or its first row is empty, and if so, returns
False
as the value cannot be found.The dimensions of the matrix are determined by calculating the number of rows and columns.
The search begins from the bottom-left corner of the matrix, initializing the row index to the last row (
r = max_rows - 1
) and the column index to the first column (c = 0
).A loop runs until the row or column indices go out of the matrix bounds:
If the current matrix element is greater than the target value, the search moves upwards by decrementing the row index (
r -= 1
).Conversely, if the current matrix element is less than the target value, the search shifts to the right by incrementing the column index (
c += 1
).If the matrix element matches the target value,
True
is returned, indicating that the value is found within the matrix.
If the loop terminates without finding the value, the function returns
False
, indicating that the value does not exist within the matrix.
This approach leverages the matrix's properties for a time-optimized search, reducing the average complexity compared to a naive search method.
No comments yet.