# Search a 2D Matrix II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/search-a-2d-matrix-ii)
Canonical: https://scaleengineer.com/dsa/problems/search-a-2d-matrix-ii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Data structures:** Array, Matrix
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [tcs](https://scaleengineer.com/companies/tcs), [Coupang](https://scaleengineer.com/companies/coupang), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Whatnot](https://scaleengineer.com/companies/whatnot)
---
## 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 in ascending from left to right.
* Integers in each column are sorted in ascending from top to bottom.

**Example 1:**

![](https://assets.glich.co/dsa/search-a-2d-matrix-ii/image0.jpg) 

**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
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/search-a-2d-matrix-ii/image1.jpg) 

**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
**Output:** false

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= n, m <= 300`
* `-109 <= matrix[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`

# Approaches
## Brute Force Approach
The simplest approach is to search every element in the matrix one by one until we find the target element.
**Time:** O(m*n) where m is number of rows and n is number of columns · **Space:** O(1) as we only use constant extra space
**Pros:** Simple to implement; No extra space required; Works for any matrix (sorted or unsorted)
**Cons:** Does not utilize the sorted property of the matrix; Very inefficient for large matrices; Checks every element even when unnecessary
### Explanation
In this approach, we iterate through each element in the matrix using nested loops. For each element, we compare it with the target value. If we find a match, we return true. If we complete the search without finding the target, we return false.

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. Iterate through each row of the matrix (i from 0 to m-1)
2. For each row, iterate through each column (j from 0 to n-1)
3. If current element equals target, return true
4. If target not found after complete iteration, return false

## Binary Search on Each Row
Since each row is sorted, we can perform binary search on each row to find the target element more efficiently than checking each element.
**Time:** O(m * log n) where m is number of rows and n is number of columns · **Space:** O(1) as we only use constant extra space
**Pros:** More efficient than brute force approach; Takes advantage of row-wise sorting; No extra space required
**Cons:** Does not utilize column-wise sorting; Still needs to check each row; Not the most efficient possible solution
### Explanation
This approach takes advantage of the fact that each row is sorted. For each row, we perform a binary search to find the target element. If the element is found in any row, we return true. If we search all rows without finding the target, we return false.

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        for (int i = 0; i < m; i++) {
            int left = 0;
            int right = n - 1;
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (matrix[i][mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. For each row in the matrix:
2. Perform binary search on the current row:
   - Calculate middle element
   - If middle element is target, return true
   - If middle element is less than target, search right half
   - If middle element is greater than target, search left half
3. If target not found in any row, return false

## Search from Top-Right Corner
We can start from the top-right corner and use both row and column sorted properties to eliminate either a row or column in each step.
**Time:** O(m + n) where m is number of rows and n is number of columns · **Space:** O(1) as we only use constant extra space
**Pros:** Most efficient solution; Utilizes both row and column sorting; Eliminates either a row or column in each step; Simple to implement
**Cons:** Must start from top-right (or bottom-left) corner; Cannot start from arbitrary position
### Explanation
This approach starts from the top-right corner of the matrix and uses both the row-wise and column-wise sorting properties. At each step, we compare the current element with the target:
- If current element equals target, we found it
- If current element is greater than target, we can eliminate the current column
- If current element is less than target, we can eliminate the current row

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        int row = 0;
        int col = n - 1;
        
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }
        return false;
    }
}
```
### Algorithm
1. Start from the top-right corner (row = 0, col = n-1)
2. While row is within bounds and col is within bounds:
   - If current element equals target, return true
   - If current element is greater than target, move left (eliminate column)
   - If current element is less than target, move down (eliminate row)
3. If we go out of bounds, return false

# Solutions
### CSharp

```csharp
public class Solution { public bool SearchMatrix ( int [][] matrix , int target ) { int m = matrix . Length , n = matrix [ 0 ]. Length ; int i = m - 1 , j = 0 ; while ( i >= 0 && j < n ) { if ( matrix [ i ][ j ] == target ) { return true ; } if ( matrix [ i ][ j ] > target ) { -- i ; } else { ++ j ; } } return false ; } }
```

### Java

```java
public class Search_a_2D_Matrix_II { public static void main ( String [] args ) { Search_a_2D_Matrix_II out = new Search_a_2D_Matrix_II (); Solution s = out . new Solution (); System . out . println ( s . searchMatrix ( new int [][]{ { 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 } }, 5 )); } /* valid in Search_a_2D_Matrix, but not in II {1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, */ class Solution { public boolean searchMatrix ( int [][] matrix , int target ) { if ( matrix == null || matrix . length == 0 || matrix [ 0 ]. length == 0 ) { return false ; } int row = matrix . length ; int col = matrix [ 0 ]. length ; int i = 0 ; int j = col - 1 ; while ( i < row && j >= 0 ) { int val = matrix [ i ][ j ]; if ( val == target ) { return true ; } else if ( target < val ) { j --; // all numbers in that column are even larger } else { i ++; // all numbers in that row are even smaller } } return false ; } } } ############ class Solution { public boolean searchMatrix ( int [][] matrix , int target ) { int m = matrix . length , n = matrix [ 0 ]. length ; int i = m - 1 , j = 0 ; while ( i >= 0 && j < n ) { if ( matrix [ i ][ j ] == target ) { return true ; } if ( matrix [ i ][ j ] > target ) { -- i ; } else { ++ j ; } } return false ; } }
```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix =
  function (matrix, target) {
    const n = matrix[0].length;
    for (const row of matrix) {
      let left = 0,
        right = n;
      while (left < right) {
        const mid = (left + right) >> 1;
        if (row[mid] >= target) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      if (left != n && row[left] == target) {
        return true;
      }
    }
    return false;
  };

```

### Python

```python
# Binary Search Variant def binarySearch ( row : List [ int ], target : int ) -> bool : left , right = 0 , len ( row ) - 1 while left <= right : mid = ( left + right ) // 2 if row [ mid ] == target : return True elif row [ mid ] < target : left = mid + 1 else : right = mid - 1 return False def searchMatrix ( matrix : List [ List [ int ]], target : int ) -> bool : for row in matrix : if binarySearch ( row , target ): return True return False ############## # start from top-right corner class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : if not matrix or not matrix [ 0 ]: return False row , col = len ( matrix ), len ( matrix [ 0 ]) i , j = 0 , col - 1 while i < row and j >= 0 : val = matrix [ i ][ j ] if val == target : return True elif target < val : j -= 1 # all numbers in that column are even larger else : i += 1 # all numbers in that row are even smaller return False # start from bottom-left corner class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : m , n = len ( matrix ), len ( matrix [ 0 ]) i , j = m - 1 , 0 while i >= 0 and j < n : if matrix [ i ][ j ] == target : return True if matrix [ i ][ j ] > target : i -= 1 else : j += 1 return False ############ class Solution ( object ): def searchMatrix ( self , matrix , target ): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ def binarySearch ( nums , target ): start , end = 0 , len ( nums ) - 1 while start + 1 < end : mid = start + ( end - start ) / 2 if nums [ mid ] > target : end = mid elif nums [ mid ] < target : start = mid else : return True if nums [ start ] == target : return True if nums [ end ] == target : return True return False for nums in matrix : if binarySearch ( nums , target ): return True return False
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/search-a-2d-matrix-ii/ // Time: O(M + N) // Space: O(1) class Solution { public: bool searchMatrix ( vector < vector < int >>& A , int target ) { int M = A . size (), N = A [ 0 ]. size (), i = 0 , j = N - 1 ; while ( i < M && j >= 0 ) { if ( A [ i ][ j ] == target ) return true ; if ( A [ i ][ j ] < target ) ++ i ; else -- j ; } return false ; } };
```