In this Leetcode Search, a 2D Matrix problem solution Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Problem solution in Python.
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: if len(matrix) == 0 or len(matrix[0]) == 0: return False row = [] # store the row with great or equal value to the target for record in matrix: if record[-1] >= target: row = record break # iterate through the row until you find the target for element in row[::-1]: if element == target: return True return False
Problem solution in Java.
class Solution { public boolean searchMatrix(int[][] matrix, int target) { //corner case if(matrix == null || matrix.length == 0) return false; if(matrix[0] == null || matrix[0].length == 0) return false; int r = matrix.length; int c = matrix[0].length; int left = 0; int right = r * c - 1; while(left <= right){ int mid = left + (right - left)/2; int value = matrix[mid / c][mid % c]; if(value == target){ return true; } else if(value < target) left = mid + 1; else right = mid -1; } return false; } }
Problem solution in C++.
class Solution { public: bool searchMatrix(vector <vector<int> >& matrix, int target) { int row = matrix.size(), col = matrix[0].size(); int left = 0, right = row * col - 1; while (left <= right) { int mid = left +(right - left)/2; int r = mid / col, c = mid % col; if (matrix[r][c]==target) return true; if (matrix[r][c] < target) left = mid +1; else right = mid -1; } return false; } };
Problem solution in C.
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){ int totalRow=matrixSize; if(totalRow==0 || *matrixColSize==0) { return false; } int start=0; int end=matrixSize*(*matrixColSize)-1; int row=0; int col= 0; int mid=0; while(start<=end) { mid=(start+end)/2; row=mid/(*matrixColSize); col=mid%(*matrixColSize); if(matrix[row][col]==target) { return true; } else if(matrix[row][col]>target) { end=mid-1; } else { start=mid+1; } } return false; }