240. Search a 2D Matrix II - cocoder39/coco39_LC GitHub Wiki

240. Search a 2D Matrix II

(i, j) is largest within rectangle (0, 0) to (i, j) and smaller within rectangle (i, j) to (m - 1, n -1). time is walk from top-right to bottom-left, O(m + n)

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = 0;
        int col = matrix[0].size() - 1;
        while (row <= matrix.size() - 1 && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            }
            if (matrix[row][col] < target) {
                row++;
            }
            else if (matrix[row][col] > target) {
                col--;
            }
        }
        return false;
    }

In order to use two moving directions to differentiate value goes up and down, we need start from bottom left or upper right.

This approach can also be used to count how many elements are smaller than target as demonstrated by option 2 in 378. Kth Smallest Element in a Sorted Matrix

⚠️ **GitHub.com Fallback** ⚠️