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

My Accepted Solution

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

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;
    }
};