Search a 2D Matrix II

• Another solution.
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if (m == 0) return false;
int n = matrix[0].size();
if (n == 0) return false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] > target) return false;
if (matrix[i][n - 1] < target) continue;
if (matrix[i][0] == target || matrix[i][n - 1] == target)
return true;
int start = 0;
int end = n - 1;
int middle = (start + end) / 2;
while (1) {
if (start == end || start == middle) {
if (matrix[i][start] == target || matrix[i][end] == target)
return true;
else break;
}
if (matrix[i][middle] == target) return true;
if (matrix[i][middle] > target) {
end = middle - 1;
}
else {
start = middle + 1;
}
middle = (start + end) / 2;
}
}
return false;
}
};

• The solution which starts searching from the top-left corner:

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] > target){
return false;
}
int row = 0;//points horizen elements
int col = 0;//points vertical elements
while(row < matrix.length-1){
if(matrix[row][0] < target){
row++;
}else{
break;
}
}
//get the max row
while(col <= matrix[0].length-1){
if(matrix[row][col] < target){
col++;
}else{
break;
}
}
//get the max col
while(row >= 0 && col < matrix[0].length){
if(matrix[row][col] == target){
return true;
}else if(matrix[row][col] > target){
row--;
}else{
col++;
}
}
return false;
}
}

• In approach 3, line number 26

``````searchRec(left, up, mid-1, down)
``````

Isn't this dividing the matrix into half rather than quarter? So how can we write recurrence relation T(x/4)?

Thanks!

• I think vertical meaning is not correct in the solution. I changed it to following:

``````class Solution(object):
def binary_search(self, matrix, target, start, vertical):
lo = start
hi = len(matrix)-1 if vertical else len(matrix[0])-1

while hi >= lo:
mid = (lo + hi)/2
if not vertical: # searching a row
if matrix[start][mid] < target:
lo = mid + 1
elif matrix[start][mid] > target:
hi = mid - 1
else:
return True
else: # searching a column
if matrix[mid][start] < target:
lo = mid + 1
elif matrix[mid][start] > target:
hi = mid - 1
else:
return True

return False

def searchMatrixBS(self, matrix, target):
# an empty matrix obviously does not contain `target`
if not matrix:
return False

for i in range(min(len(matrix), len(matrix[0]))):
vertical_found = self.binary_search(matrix, target, i, True)
horizontal_found = self.binary_search(matrix, target, i, False)
if vertical_found or horizontal_found:
return True

return False
``````

• for Search Space Reduction, for the same reason you can start from top right as well

• Another Divide and Conquer. Every time split the matrix into 4 parts. Using binary tree idea search idea in the 2D matrix. The complexity should be O(max(m,n)). Accepted solution as following:

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length<=0 || matrix[0].length <=0)
{
return false;
}
return searchSubMatrix(matrix, target, 0, 0, matrix.length, matrix[0].length);
}

``````private boolean searchSubMatrix(int[][] matrix, int target, int startR, int startC, int rows,int columns)
{
if(matrix[startR][startC] == target)
{
return true;
}

//the up left is the smallest item and bottom right is the largest one.
if((columns <= 1 && rows <= 1)
|| !((matrix[startR+rows-1][startC + columns-1]>= target)&&(matrix[startR][startC]<=target)))
{
return false;
}
int newRows = rows/2+rows%2;
int newColumns = columns/2+columns%2;
return searchSubMatrix(matrix, target, startR, startC, newRows, newColumns)
|| searchSubMatrix(matrix, target, startR + rows/2, startC, newRows, newColumns)
|| searchSubMatrix(matrix, target, startR + rows/2, startC+columns/2, newRows, newColumns)
|| searchSubMatrix(matrix, target, startR, startC+columns/2, newRows, newColumns);
}
``````

}

• Sorry, the complexity is O(log(max(m,n)))

• In Approach 3, Should it be 'searchRec(left, row, mid-1, down)' instead of 'searchRec(left, up, mid-1, down)'?? Otherwise you are recursing the 3/4 area of the original matrix...

• Tried solution 4 to count the number of occurrences of a target in a 2D array. I am getting the time limit exceeded error.

• But Brute force approach worked. Made slight modification to include counts

class Solution:
def searchMatrix(self, matrix, target):
count = 0
if len(matrix) == 0 or len(matrix[0]) == 0:
return 0
for row in matrix:
if target in row:
count+=1
return count

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.