In this post, we are going to solve the 74. Search a 2D Matrix problem of Leetcode. This problem 74. Search a 2D Matrix is a Leetcode medium level problem. Let’s see the code, 74. Search a 2D Matrix – Leetcode Solution.
Problem
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 from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1 :
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2 :
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Constraints
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
Now, let’s see the code of 74. Search a 2D Matrix – Leetcode Solution.
Search a 2D Matrix – Leetcode Solution
74. Search a 2D Matrix – Solution in Java
class Solution { public boolean bs(int[][] matrix,int row, int start, int end, int target){ while(start <= end){ int mid = start - ( start - end) / 2; if(target == matrix[row][mid]) return true; else if(target < matrix[row][mid]) end = mid-1; else if(target > matrix[row][mid]) start = start + 1; } return false; } public boolean searchMatrix(int[][] matrix, int target) { //finding potential row int m = matrix[0].length-1; int sRow = 0; int eRow = matrix.length-1; while(sRow <= eRow){ int mid = sRow - (sRow - eRow)/2; if(target == matrix[mid][0] || target == matrix[mid][m]) return true; else if(target > matrix[mid][0] && target < matrix[mid][m]){ return bs(matrix, mid, 0, m, target); } else if(target < matrix[mid][0]){ eRow = mid - 1; } else if(target > matrix[mid][m]){ sRow = mid + 1; } } return false; } }
74. Search a 2D Matrix – Solution in C++
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int n = matrix.size(); int m = matrix[0].size(); if(n == 0 || m == 0) return false; int start = 0, end = m*n - 1; while(start <= end) { int mid = start + (end - start) / 2; int ind = matrix[mid/m][mid%m]; if (target == ind) return true; else if(target < ind) end = mid - 1; else start = mid + 1; } return false; } };
74. Search a 2D Matrix – Solution in Python
class Solution: def searchMatrix(self, matrix, target): if not matrix or not matrix[0]: return False m, n = len(matrix[0]), len(matrix) beg, end = 0, m*n - 1 while beg < end: mid = (beg + end)//2 if matrix[mid//m][mid%m] < target: beg = mid + 1 else: end = mid return matrix[beg//m][beg%m] == target
Note: This problem 74. Search a 2D Matrix is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.