This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 141. This is a Leet code problem named Search a 2D Matrix We will solve it using python and it is the best space and time-optimized solution.
Question of Search a 2D Matrix
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.
Given an element “x” and a sorted matrix mat[n][m]. If x is present, locate its location in the matrix; otherwise, display -1. The matrix is arranged so that each row’s elements are arranged in ascending order, and for row I where 1 = I = n-1, the first element of row I is larger than or equal to the last element of row i-1.
We can see that any number (let’s say k) we are looking for must be included inside a row, containing both the start and end parts of the row (if it exists at all). In order to search in that row, we first use linear search to determine the row in which k must be located (n), and then we use linear search once again (O(m)).
Algorithm
This method performs the following steps for a given input array:
Initialize n with a number of elements in a row.
Run for loop for each row of a matrix at a time.
check the condition if the target number is in between or equal to the first and last element.
if yes then search the target number for each value of rows.
if found return true
end for loop
return false
Python Code for Search a 2D Matrix
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
#number of elements in a row starting from zero
n = len(matrix[0])-1
#for loop for row at a time
for rows in matrix:
#check condition if target is in between first and last element
if(rows[0]<= target and rows[n]>=target):
#if yes then search target for each val of rows
for val in rows:
#if found return true
if(val==target):
return True
return False
