# Search a 2D Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/search-a-2d-matrix)
Canonical: https://scaleengineer.com/dsa/problems/search-a-2d-matrix
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Matrix
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Grab](https://scaleengineer.com/companies/grab), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Nutanix](https://scaleengineer.com/companies/nutanix), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Yandex](https://scaleengineer.com/companies/yandex), [Coupang](https://scaleengineer.com/companies/coupang), [Snap](https://scaleengineer.com/companies/snap), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## Problem
You are given an `m x n` integer matrix `matrix` with the following two properties:

* Each row is sorted in non-decreasing order.
* The first integer of each row is greater than the last integer of the previous row.

Given an integer `target`, return `true` _if_ `target` _is in_ `matrix` _or_ `false` _otherwise_.

You must write a solution in `O(log(m * n))` time complexity.

**Example 1:**

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

**Input:** matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
**Output:** true

**Example 2:**

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

**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`
* `-104 <= matrix[i][j], target <= 104`

# Approaches
## Brute Force Iteration
This is the most straightforward but least efficient approach. We can simply iterate through every cell of the `m x n` matrix and check if the element at that cell is equal to the `target`. This method does not take advantage of the matrix's special sorted structure.
**Time:** O(m * n) · **Space:** O(1)
**Pros:** Very simple to understand and implement.; Works on any 2D matrix, regardless of whether it's sorted or not.
**Cons:** Highly inefficient as it does not leverage the sorted properties of the matrix.; Fails to meet the `O(log(m * n))` time complexity requirement specified in the problem description.
### Explanation
The algorithm uses two nested loops to traverse the matrix. The outer loop iterates through the rows from index `0` to `m-1`, and the inner loop iterates through the columns from index `0` to `n-1`. In each iteration of the inner loop, we compare the current element `matrix[row][col]` with the `target` value. If they are equal, we have found the target and can return `true`. If we traverse the entire matrix and do not find the target, the loops will complete, and we return `false`.

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) {
            return false;
        }
        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
- Get the dimensions of the matrix, `m` (rows) and `n` (columns).
- Iterate through each row `i` from `0` to `m-1` using a for loop.
- For each row `i`, iterate through each column `j` from `0` to `n-1` using a nested for loop.
- Inside the inner loop, check if the element `matrix[i][j]` is equal to the `target`.
- If a match is found, return `true` immediately.
- If the loops complete without finding the `target`, return `false` after the loops finish.

## Binary Search on Each Row
A better approach than brute force is to leverage the fact that each row is sorted. We can iterate through each row and, for each one, perform an efficient binary search to check for the `target`'s presence. This avoids a linear scan of every single element.
**Time:** O(m * log(n)) · **Space:** O(1)
**Pros:** More efficient than the brute-force approach.; Effectively uses the sorted property of individual rows.
**Cons:** Does not utilize the property that rows are sorted with respect to each other (i.e., `matrix[i-1][n-1] < matrix[i][0]`).; The time complexity does not meet the `O(log(m * n))` requirement for all cases, especially when `m` is large.
### Explanation
This method involves a linear scan of the rows. For each row, we first perform a quick check to see if the `target` could even exist in that row. Since each row is sorted, the `target` must be greater than or equal to the first element and less than or equal to the last element. If this condition holds, we then apply a binary search on that specific row. If the binary search finds the element, we return `true`. If we iterate through all the rows without finding the target, we conclude it's not in the matrix and return `false`.

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) {
            return false;
        }
        int n = matrix[0].length;

        for (int i = 0; i < m; i++) {
            if (n > 0 && target >= matrix[i][0] && target <= matrix[i][n - 1]) {
                int low = 0, high = n - 1;
                while (low <= high) {
                    int mid = low + (high - low) / 2;
                    if (matrix[i][mid] == target) {
                        return true;
                    } else if (matrix[i][mid] < target) {
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- Iterate through each row `i` of the matrix from `0` to `m-1`.
- For each row, check if the `target` could potentially be in that row. This can be done by checking if `target` is between the first (`matrix[i][0]`) and last (`matrix[i][n-1]`) elements of the row.
- If the `target` is within the range of the current row, perform a standard binary search on that row `matrix[i]`.
- If the binary search finds the `target`, return `true`.
- If the loop finishes after checking all rows and the `target` is not found, return `false`.

## Two-Step Binary Search
This approach fully utilizes both sorted properties of the matrix to achieve the desired logarithmic time complexity. It involves two phases of binary search: first to find the correct row where the target might exist, and second to find the target within that specific row.
**Time:** O(log(m) + log(n)) · **Space:** O(1)
**Pros:** Highly efficient, meeting the problem's time complexity requirement.; Logically separates the problem into two smaller, manageable binary searches.
**Cons:** The implementation is slightly more complex as it involves two separate binary search logics.
### Explanation
The key insight is that we can first narrow down the search to a single row. Since the first element of each row is greater than the last element of the previous row, we can perform a binary search on the rows themselves. We search for a row `i` such that `matrix[i][0] <= target <= matrix[i][n-1]`. This first binary search takes `O(log m)` time. Once we identify this potential row, we perform a second, standard binary search on this row's elements to find the `target`. This second search takes `O(log n)` time. The total time complexity is the sum of these two searches.

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) return false;
        int n = matrix[0].length;
        if (n == 0) return false;

        // Binary search to find the row
        int top = 0, bottom = m - 1;
        int targetRow = -1;
        while (top <= bottom) {
            int midRow = top + (bottom - top) / 2;
            if (target >= matrix[midRow][0] && target <= matrix[midRow][n - 1]) {
                targetRow = midRow;
                break;
            } else if (target < matrix[midRow][0]) {
                bottom = midRow - 1;
            } else {
                top = midRow + 1;
            }
        }

        if (targetRow == -1) {
            return false; // Target is not in the range of any row
        }

        // Binary search within the identified row
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[targetRow][mid] == target) {
                return true;
            } else if (matrix[targetRow][mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}
```
### Algorithm
- **Step 1: Find the Row.** Perform a binary search on the rows of the matrix (from index `0` to `m-1`).
  - For a middle row `mid`, compare `target` with the first (`matrix[mid][0]`) and last (`matrix[mid][n-1]`) elements of that row.
  - If `target < matrix[mid][0]`, the target must be in an earlier row, so adjust the search space to the upper half.
  - If `target > matrix[mid][n-1]`, the target must be in a later row, so adjust the search space to the lower half.
  - If `matrix[mid][0] <= target <= matrix[mid][n-1]`, we have found the correct row. Store this row index and proceed to Step 2.
- **Step 2: Find the Element.** Perform a standard binary search for the `target` within the row identified in Step 1.
- If the `target` is found in Step 2, return `true`.
- If no suitable row is found in Step 1, or the `target` is not found in Step 2, return `false`.

## Treat as a Sorted 1D Array
This is arguably the most elegant and efficient approach. The matrix's properties guarantee that if we were to flatten it into a single list, that list would be sorted. We can perform a single binary search on this "virtual" 1D array without actually creating it in memory.
**Time:** O(log(m * n)) · **Space:** O(1)
**Pros:** Most efficient and concise solution.; Implemented with a single, clean binary search loop.; Directly addresses the problem as a search in a single sorted space, which is the core of binary search.
**Cons:** Requires understanding the mapping from a 1D index to 2D coordinates, which might be slightly less intuitive at first glance.
### Explanation
We can treat the `m x n` matrix as a sorted 1D array of size `m * n`. The binary search will operate on indices from `0` to `m * n - 1`. The main challenge is to map a 1D index from our binary search back to the 2D matrix coordinates `(row, col)`. This mapping is straightforward: for a given 1D index `k` and a matrix with `n` columns, the corresponding `row` is `k / n` and the `col` is `k % n`. With this mapping, we can perform a standard binary search on the range of indices, comparing `matrix[mid / n][mid % n]` with the `target` in each step to narrow down the search space.

```java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m == 0) {
            return false;
        }
        int n = matrix[0].length;

        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midElement = matrix[mid / n][mid % n];

            if (midElement == target) {
                return true;
            } else if (midElement < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize two pointers, `left = 0` and `right = m * n - 1`, representing the start and end of the virtual 1D array.
- While `left <= right`:
  - Calculate the middle index `mid = left + (right - left) / 2`.
  - Convert the 1D index `mid` to 2D coordinates: `row = mid / n`, `col = mid % n`.
  - Get the element `val = matrix[row][col]`.
  - If `val == target`, return `true`.
  - If `val < target`, the target must be in the right half, so move the `left` pointer to `mid + 1`.
  - If `val > target`, the target must be in the left half, so move the `right` pointer to `mid - 1`.
- If the loop terminates, the target was not found, so return `false`.

# Solutions
### Java

```java
class Solution { public boolean searchMatrix ( int [][] matrix , int target ) { int m = matrix . length , n = matrix [ 0 ]. length ; int left = 0 , right = m * n - 1 ; while ( left < right ) { int mid = ( left + right ) >> 1 ; int x = mid / n , y = mid % n ; if ( matrix [ x ][ y ] >= target ) { right = mid ; } else { left = mid + 1 ; } } return matrix [ left / n ][ left % n ] == target ; } }
```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var searchMatrix =
  function (matrix, target) {
    const m = matrix.length,
      n = matrix[0].length;
    let left = 0,
      right = m * n - 1;
    while (left < right) {
      const mid = (left + right + 1) >> 1;
      const x = Math.floor(mid / n);
      const y = mid % n;
      if (matrix[x][y] <= target) {
        left = mid;
      } else {
        right = mid - 1;
      }
    }
    return matrix[Math.floor(left / n)][left % n] == target;
  };

```

### CPP

```cpp
class Solution { public: bool searchMatrix ( vector < vector < int >>& matrix , int target ) { int m = matrix . size (), n = matrix [ 0 ]. size (); int left = 0 , right = m * n - 1 ; while ( left < right ) { int mid = left + right >> 1 ; int x = mid / n , y = mid % n ; if ( matrix [ x ][ y ] >= target ) { right = mid ; } else { left = mid + 1 ; } } return matrix [ left / n ][ left % n ] == target ; } };
```

### Python

```python
class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : m , n = len ( matrix ), len ( matrix [ 0 ]) left , right = 0 , m * n - 1 while left <= right : # must be <=, not <, for matrax=[[1]],target=1 mid = ( left + right ) >> 1 x , y = divmod ( mid , n ) # note: divide column count if matrix [ x ][ y ] == target : return True elif matrix [ x ][ y ] > target : right = mid - 1 else : left = mid + 1 return False ########### class Solution : def searchMatrix ( self , matrix : List [ List [ int ]], target : int ) -> bool : m , n = len ( matrix ), len ( matrix [ 0 ]) left , right = 0 , m * n - 1 while left < right : mid = ( left + right ) >> 1 x , y = divmod ( mid , n ) if matrix [ x ][ y ] >= target : right = mid else : left = mid + 1 return matrix [ left // n ][ left % n ] == target
```