Search a 2D Matrix (Leet Code-74)

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.

Example

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
-10⁴ <= matrix[i][j], target <= 10⁴

Approach to solveSearch a 2D Matrix

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