Search a 2D Matrix II

[ymolliks]

Ideas

1. Linear Time Solution

Solution

Let $\tt m = |rows|$ and $\tt n = |columns|$.

We will start at $\tt matrix[r = 0][c = n-1]$ and will do the followings:

1. If $\tt matrix[r][c] == target$, then we have found our answer!
2. Or, if $\tt matrix[r][c] > target$, then set $\tt c = c -1$. Because, since columns are sorted in ascending order from top to bottom, there is no ways we will find $\tt target$ in this column $\tt c$.
3. And, if $\tt matrix[r][c] < target$, then set $\tt r = r -1$. That's because the only way we can find $\tt matrix[r][c] == target$ is to going to the rows below.
4. Repeat previous 3 steps until either we find the answer or $\tt r == m$ or $\tt c < 0$.

Implementation

class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();

        int r = 0, c = n - 1;
        while (r < m && c >= 0) {
            if (matrix[r][c] == target)
                return true;
            if (matrix[r][c] < target)
                r++;
            else c--;
        }
        return false;
    }
};

Complexity

Time: $\tt O(|row|\times|column|)$

Space: $\tt O(1)$

[ymolliks]

Search a 2D Matrix II