74. Search a 2D Matrix (Solution || Leetcode medium || Java)

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

SOLUTION:

As the matrix is sorted, hence, with no doubt we will apply binary search for finding target

class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].length — 1;

while(row < matrix.length){//finding the row in which the element may lie

if(target <= matrix[row][col]){//if the row found apply binary search in that row
return binarySearch(matrix,target,row);
}else{
row++;
}
}
return false;
}

public boolean binarySearch(int[][] matrix, int target, int row){
int start = 0;
int end = matrix[0].length — 1;

while(start <= end){//applying binary search for target
int mid = start + (end — start)/2;

if(target == matrix[row][mid]){
return true;//if element found return true
}else if(target < matrix[row][mid]){
end = mid — 1;
}else{
start = mid + 1;
}
}
return false;//if element doesn’t exist return false
}
}

TIME COMPLEXITY :- O(log(n))

SPACE COMPLEXITY :- O(1)

Thank you for reading. If you have any queries, then please let me know in the comment section, I will surely response toward that.