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.
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
Analysis written by: @awice.