# 240 Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an `mxn`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.

For example,

Consider the following 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]
]
```

Given **target**=`5`, return`true`.

Given **target**=`20`, return`false`.

**The Idea:** Zig zag through the matrix (eliminate rows and columns) until we either find or exceed the bounds of the matrix. If we start from the upper right corner, we can deduce two things. First, since the else element of every row contains the max element of the row it is under, if that target is greater than that element, then no other element in the row are guaranteed to match it. Therefore the only option is to move down one row, where this element is greater than it. Secondly, if the element is otherwise smaller than the target, then we can deduce that the elements in the column beneath it are all greater. So likewise, the only option would be to move left.

[![](http://4.bp.blogspot.com/_UElib2WLeDE/TK6IxlaUjRI/AAAAAAAACWk/xQkntM5OeC8/s1600/matrix_hi5.png)](http://4.bp.blogspot.com/_UElib2WLeDE/TK6IxlaUjRI/AAAAAAAACWk/xQkntM5OeC8/s1600/matrix_hi5.png)

**Complexity:** O(n+m) time. Consider the worst case occurance of the element on the bottom-left. O(1) space.

```python
def searchMatrix(self, matrix, target):
    """
    :type matrix: List[List[int]]
    :type target: int
    :rtype: bool
    """

    if len(matrix) == 0 or (len(matrix) == 1 and len(matrix[0]) == 0):
        return False

    rows = len(matrix)
    cols = len(matrix[0])

    r = 0
    c = cols - 1

    while c >= 0 and r < rows:
        if matrix[r][c] < target:
            r += 1
        elif matrix[r][c] > target:
            c -= 1
        else:
            return True

    return False
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/240-search-a-2d-matrix-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.