240. Search a 2D Matrix II

1. 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.

2. Example

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

3. Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10$^{9}$ <= matix[i][j] <= 10$^{9}$
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• -10$^{9}$ <= target <= 10$^{9}$

4. Solutions

Queue

m = i_matrix.size(), n = i_matrix.front().size()
Time complexity: O(m + n)
Space complexity: O(1)

use the right-top(or the left-down) point as a pivot to exclude values quickly, that’s because all left values in the same line are smaller than it, and all down values in the same column are bigger than it

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution
{
public:
    // bool searchMatrix(vector<vector<int>>& matrix, int target)
    bool searchMatrix(vector<vector<int>> &i_matrix, int target)
    {
        if(i_matrix.empty() || i_matrix.front().empty()) return false;

        const int rows = i_matrix.size();
        const int colums = i_matrix.front().size();
        for(int i = 0, j = colums - 1; i < rows && j >= 0; )
        {
            if(i_matrix[i][j] == target) return true;

            i_matrix[i][j] < target ? i++ : j--;
        }

        return false;
    }
};