Leetcode : Search a 2D Matrix II
Published: 2021-08-26 16:42:44

**Problem statement**

Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

* Integers in each row are sorted in ascending from **left to right**.
* Integers in each column are sorted in ascending from **top to bottom**.

***

**Example:1**

> Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5

> ![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8yo8n5nm74nt7by0nqxa.png)

> Output: **true**


**Example:2**

> Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20

> ![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hkrx4tkhoffmeyyrwwgh.png)

> Output: **false**

***

**Constraints**

  * m == matrix.length
  * n == matrix[i].length
  * 1 <= n, m <= 300
  * -109 <= matix[i][j] <= 109
  * All the integers in each row are sorted in ascending order.
  * All the integers in each column are sorted in ascending order.
  * -109 <= target <= 109.

***

[Link to the question on Leetcode](https://leetcode.com/problems/search-a-2d-matrix-ii/)

***

**Idea**

> ######Bruteforce solution : The bruteforce solution for this problem is directly checking each cell of the matrix and return **True** if target is found or else return **False**.

> ######Time complexity : O(M*N) , M = number of rows , n = number of columns.

***

> Optimized solution for this problem is, as per the problem statement rows and columns are sorted from **left to right** and **top to bottom** , we can directly do binary search on each row.

> ######Time complexity : **O(M logN)** , M = number of rows , n = number of columns.

***

> We can still optimize this solution to **O(M+N)**.Lets discuss that solution with below example.

> ![Input](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zhv7257tz6e5dacc5o4e.jpeg)

> Lets initialize two variables i and j as first row and last column as below.

> ![Initialization](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3o5s146hiyf9t98ibdtd.jpeg)

> Since **target** is less the **current cell** we move to the left in the matrix (as rows and columns are sorted from left to right and top to bottom)

> ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sb4pgz9wiik970nqtgk8.jpeg)

> Since **target** is greater than **current cell value** we move to the next row.

> ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/smskt3oyd298am9k4fj4.jpeg)

> Since **target** is still greater than the **current cell value** , we again move down the matrix.

> ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i1hyytjnk24gmfdrvrq5.jpeg)

> Now **target** is less than the **current cell value** , so we move towards the left of the matrix within the current row.

> ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ioghpyaoi5ejmhqgmwn9.jpeg)

> Now **target** is greater than the **current cell value** , so we move down the matrix within the same column.

> ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2v968rshd36tqk17t2s6.jpeg)

> Now **target** is less than the **current cell value** , so we move to the left of the matrix within the current row.

> ![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pu4tt4ybb7ba0188o7rl.jpeg)

> At this point , we got cell whose value is equal to **target** , so we return **True**

> So the overall idea here is whenever we encounter a cell whose value is greater than **target** we move towards the left within the same row having said that **columns are sorted from top to bottom** (so we are sure that we will not get the target element if move down the matrix , so we move to the left) and whenever we encounter a cell whose value is less than the **target** we move down the matrix as **rows are sorted from left to right**(as we can guarantee that moving left will not give us the target element).

**Code** - **Python**

```python
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])
        i = 0
        j = cols-1
        while i >= 0 and j >= 0 and i < rows:
            cell_value = matrix[i][j]
            if cell_value == target:
                return True
            elif cell_value > target:
                j -= 1
            else:
                i += 1
        return False
        
```
***
Please like this post if you found this informative.