> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/201-300/search-a-2d-matrix-ii.md).

# 240. Search a 2D Matrix II

### Description

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.

### 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`

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/search-a-2d-matrix-ii/)
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:**&#x20;

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

<div align="left"><img src="/files/-MUEy8h01hJkuyhxpWJr" alt=""></div>
{% endtab %}

{% tab title="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

**Output:** false

<div align="left"><img src="/files/-MUEzGXr8yDRRP7LTWCm" alt=""></div>
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : O(1)
 */

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        for(int[] arr: matrix) {
            if(binarySearch(arr, target) != -1) {
                return true;
            }
        }
        return false;
    }
    
    private int binarySearch(int[] arr, int key) {
        int n = arr.length;
        if(key < arr[0] || key > arr[n-1]) {
            return -1;
        }
        int low = 0, high = n-1;
        while(low <= high) {
            int mid = (low + high)/2;
            if(arr[mid] == key) {
                return mid;
            }
            if(arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n+m)
 * Space complexity : O(1)
 */

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-1, col = 0;
        
        while(row >= 0 && col < matrix[0].length) {
            int value = matrix[row][col];
            if(value > target) {
                row--;
            } else if(value < target) {
                col++;
            } else {
                return true;
            }
        }
        return false;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*