Approach #1: Row and Column Maximums [Accepted]
Intuition and Algorithm
The skyline looking from the top is col_maxes = [max(column_0), max(column_1), ...]
. Similarly, the skyline from the left is row_maxes [max(row_0), max(row_1), ...]
In particular, each building grid[r][c]
could become height min(max(row_r), max(col_c))
, and this is the largest such height. If it were larger, say grid[r][c] > max(row_r)
, then the part of the skyline row_maxes = [..., max(row_r), ...]
would change.
These increases are also independent (none of them change the skyline), so we can perform them independently.
Complexity Analysis

Time Complexity: , where is the number of rows (and columns) of the grid. We iterate through every cell of the grid.

Space Complexity: , the space used by
row_maxes
andcol_maxes
.
Analysis written by: @awice.