807. Max Increase to Keep City Skyline 

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
class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int n = grid.length;

        int[] rowMaxArray = new int[n];
        int[] colMaxArray = new int[n];

        for (int i = 0; i < n; i++) {
            int rowMax = 0, colMax = 0;
            for (int j = 0; j < n; j++) {
                rowMax = Math.max(rowMax, grid[i][j]);
                colMax = Math.max(colMax, grid[j][i]);
            }
            rowMaxArray[i] = rowMax;
            colMaxArray[i] = colMax;
        }

        int maxIncrease = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                maxIncrease += Math.min(rowMaxArray[i], colMaxArray[j]) - grid[i][j];
            }
        }
        return maxIncrease;
    }
}

References

807. Max Increase to Keep City Skyline