In this post, we are going to solve the Search a 2D Matrix Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

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 leetcode solution of Search a 2D Matrix Leetcode Solution.
Search a 2D Matrix Leetcode 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
Search a 2D Matrix Leetcode Solution in CPP
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; } };
Search a 2D Matrix Leetcode 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; } }
Note: This problem Search a 2D Matrix is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.