grid47 Exploring patterns and algorithms
Oct 30, 2024
5 min read
Solution to LeetCode 74: Search a 2D Matrix Problem
You are given an m x n matrix where 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 a target integer, return true if the target exists in the matrix or false otherwise. The solution must have a time complexity of O(log(m * n)).
Problem
Approach
Steps
Complexity
Input: You are given a matrix of size m x n with sorted rows and specific order between consecutive rows.
• Explanation: The target 8 is not present in the matrix, so the answer is false.
Approach: To achieve the required time complexity of O(log(m * n)), we can treat the matrix as a flattened array and apply binary search over it.
Observations:
• The matrix has sorted rows and columns.
• A simple binary search over the matrix could help find the target efficiently.
• By viewing the matrix as a 1D array, binary search can be applied directly to find the target with O(log(m * n)) complexity.
Steps:
• Identify the size of the matrix (m x n).
• Calculate the left (l) and right (r) pointers for binary search over the entire matrix (flattened view).
• Perform binary search by calculating the mid index and mapping it to the appropriate row and column in the matrix.
• Return true if the target is found, else continue searching.
Empty Inputs:
• If the matrix is empty, return false immediately.
Large Inputs:
• Consider the performance of the binary search when the matrix size is at the upper limit (100 x 100).
Special Values:
• Ensure that the target value falls within the allowed range (-104 to 104).
Constraints:
• The function must run in O(log(m * n)) time.
boolsearchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int left =0, right = m * n -1;
while (left <= right) {
int mid = left + (right - left) /2;
int row = mid / n, col = mid % n;
if (matrix[row][col] == target) {
returntrue;
} elseif (matrix[row][col] < target) {
left = mid +1;
} else {
right = mid -1;
}
}
returnfalse;
}
1 : Function Declaration
boolsearchMatrix(vector<vector<int>>& matrix, int target) {
Declares a function `searchMatrix` that takes a 2D matrix and a target value as input and returns a boolean indicating whether the target is found.
2 : Variable Initialization
int m = matrix.size(), n = matrix[0].size();
Initializes variables `m` and `n` to store the number of rows and columns in the matrix.
3 : Variable Initialization
int left =0, right = m * n -1;
Initializes two pointers `left` and `right` to represent the search range within the matrix, treated as a 1D array.
4 : Loop Iteration
while (left <= right) {
Starts a `while` loop to perform binary search.
5 : Calculation
int mid = left + (right - left) /2;
Calculates the middle index `mid` using integer division to prevent overflow.
6 : Index Calculation
int row = mid / n, col = mid % n;
Calculates the row and column indices corresponding to the `mid` index in the 1D representation.
7 : Condition
if (matrix[row][col] == target) {
Checks if the element at the `mid` index is equal to the target value.
8 : Return
returntrue;
If the target is found, returns `true`.
9 : Conditional
} elseif (matrix[row][col] < target) {
If the element at `mid` is less than the target, the target must be in the right half of the search space.
10 : Index Update
left = mid +1;
Adjusts the `left` pointer to the middle index plus 1.
11 : Conditional
} else {
If the element at `mid` is greater than the target, the target must be in the left half of the search space.
12 : Index Update
right = mid -1;
Adjusts the `right` pointer to the middle index minus 1.
13 : Loop Iteration
}
Continues the loop until the target is found or the search space is exhausted.
14 : Return
returnfalse;
If the target is not found after the loop, returns `false`.
Best Case: O(log(m * n))
Average Case: O(log(m * n))
Worst Case: O(log(m * n))
Description: The time complexity is O(log(m * n)) because we perform binary search over the matrix treated as a 1D array.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as the binary search is performed in place with no extra space required.
