Counting the Big Numbers (Largests in Its Row and Column) in a Matrix

Given a two-dimensional integer matrix, return the total number of integers whose value is the largest in its row and in its column. For example, given
1 3 2
4 6 5
1 5 7
Return 2 since 6 and 7 meet the criteria.

Constraints
The number of rows in matrix is at most 200
The number of columns in matrix is at most 200
Example 1
Input

1 2 3 4 5

matrix = [     [1, 3, 2],     [6, 6, 5],     [1, 5, 7] ]

matrix = [
    [1, 3, 2],
    [6, 6, 5],
    [1, 5, 7]
]

Output
3
Explanation
The 3 big numbers are 6, 6, and 7.

Algorithm to Count the Big Numbers in 2-Dimensional Array/Matrix

We can perform one scan through each element in the 2D matrix and record the maximum value in each columns and rows, hence using O(R + C) space where R is the number of rows, and C is the number of columns. Then a second pass to increment the counter if the element equals both the maximum in its column and row.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int solve(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return 0;
    int cols = matrix[0].size();
    vector<int> rowMax(rows, 0);
    vector<int> colMax(cols, 0);
    int ans = 0;
    for (int r = 0; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            rowMax[r] = max(rowMax[r], matrix[r][c]);
            colMax[c] = max(colMax[c], matrix[r][c]);
        }
    }
    for (int r = 0; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            if (matrix[r][c] == rowMax[r] && matrix[r][c] == colMax[c]) {
                ans ++;
            }
        }
    }
    return ans;
}

int solve(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    if (rows == 0) return 0;
    int cols = matrix[0].size();
    vector<int> rowMax(rows, 0);
    vector<int> colMax(cols, 0);
    int ans = 0;
    for (int r = 0; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            rowMax[r] = max(rowMax[r], matrix[r][c]);
            colMax[c] = max(colMax[c], matrix[r][c]);
        }
    }
    for (int r = 0; r < rows; ++ r) {
        for (int c = 0; c < cols; ++ c) {
            if (matrix[r][c] == rowMax[r] && matrix[r][c] == colMax[c]) {
                ans ++;
            }
        }
    }
    return ans;
}

The time complexity of such counting algorithm is O(RC) and space complexity is also O(RC).

–EOF (The Ultimate Computing & Technology Blog) —