74. Search a 2D Matrix

1. Description

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

2. Example

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

Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

3. Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• $-10^4$ <= matrix[i][j], target <= $10^4$

4. Solutions

My Accepted Solution

n is the number of elements in i_matrix
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    bool searchMatrix(const vector<vector<int>>& i_matrix, int target) {
        const int rows = i_matrix.size(), columns = i_matrix.front().size();

        for (int i = 0, j = columns - 1; i < rows && j >= 0;) {
            if (i_matrix[i][j] == target) {
                return true;
            }

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

        return false;
    }
};