Algorithm

LintCode/Search A 2D matrix II

Problem Summary

Search for the value T in an M x N matrix and return the occurrence of it.

This matrix has the following properties:

  1. Integers in each row are sorted from left to right.
  2. Integers in each column are sorted from up to bottom.
  3. No duplicate integers in each row or column.

Solution

We can use two values i and j to mark the current position we are at. And we use the following algorithm.

  1. Let i = 0 and j = N-1.
  2. If matrix[i][0] > T , then the search is finished (Because of the property 2 of the matrix).
  3. While matrix[i][j] > T and j ≥ 0 , decrease j by 1.
  4. If j < 0 , then finish the search.
  5. If matrix[i][j] == T, then increase the answer by 1.
  6. Increase i by 1 and if i < M, go back to step 2.

Note that, because the matrix has property 2, we do not need to set j to N-1 every time we increase i.

The time complexity is O(M+N) and only constant extra space is needed.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    /*
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector<vector<int>> &matrix, int target) {
        int m = matrix.size();
        if (m==0)
            return 0;
        int n = matrix[0].size();
        int i = 0, j = n-1, ans = 0;
        while (i<m && j>=0) {
            if (matrix[i][0] > target)
                break;
            while (j>=0 && matrix[i][j] > target)
                --j;
            if (j<0)
                break;
            if (matrix[i][j]==target)
                ++ans;
            ++i;
        }
        return ans;
    }
};