We are given an n × m integer matrix. In one operation, we may select a single row and a single column, subtract 1 from every element in that row and every element in that column — except the intersection cell, which is only decremented once (i.e., no double subtraction). Our goal is to minimize the maximum value in the resulting matrix.

Key Insight: Greedy Selection Guided by Max-Value Coverage

The optimal strategy hinges on reducing as many occurrences of the original global maximum M as possible. Since each operation affects one full row and one full column, the number of M-valued cells reduced equals:

count_row[r] + count_col[c] − (1 if matrix[r][c] == M else 0)

where count_row[r] is the number of times M appears in row r, and similarly for count_col[c].

Thus, instead of brute-forcing all O(nm) row-column pairs naively, we precompute:

• rowMaxCount[i]: number of columns j where matrix[i][j] == M
• colMaxCount[j]: number of rows i where matrix[i][j] == M

Then, for each candidate pair (i, j), compute effective coverage:

coverage = rowMaxCount[i] + colMaxCount[j] - (matrix[i][j] == M ? 1 : 0);

We prioritize candidates with maximal coverage. If multiple pairs tie, we break the tie by evaluating the actual post-operation maximum — because higher coverage doesn’t always guarantee lower final max (as shown in edge cases).

Efficient Evaluation

For each top-k candidate pair (we only need to check those with coverage ≥ max_coverage − 1, since diminishing returns apply), simulate the subtraction:

• For all j': new_matrix[i][j'] = matrix[i][j'] − 1
• For all i': new_matrix[i'][j] = matrix[i'][j] − 1
• Then restore overlap: new_matrix[i][j] += 1

Track the maximum in O(nm) per candidate — but since we restrict candidates to at most O(n + m) high-coverage options, total complexity remains O((n + m) ⋅ nm) = O(n²m + nm²), which is acceptable for typical constraints (e.g., n, m ≤ 100).

Implementation Snippet

#include <vector>
#include <algorithm>
#include <climits>

int solve(const std::vector<std::vector<int>>& mat) {
    int n = mat.size(), m = mat[0].size();
    int global_max = INT_MIN;
    for (const auto& row : mat)
        for (int x : row) global_max = std::max(global_max, x);

    std::vector<int> rowCnt(n, 0), colCnt(m, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (mat[i][j] == global_max) {
                rowCnt[i]++;
                colCnt[j]++;
            }
        }
    }

    int bestCoverage = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            bestCoverage = std::max(bestCoverage,
                rowCnt[i] + colCnt[j] - (mat[i][j] == global_max));

    int ans = INT_MAX;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int cov = rowCnt[i] + colCnt[j] - (mat[i][j] == global_max);
            if (cov < bestCoverage - 1) continue;

            int curMax = INT_MIN;
            for (int x = 0; x < n; ++x) {
                for (int y = 0; y < m; ++y) {
                    int val = mat[x][y] - (x == i) - (y == j);
                    curMax = std::max(curMax, val);
                }
            }
            ans = std::min(ans, curMax);
        }
    }
    return ans;
}