Raise Towers, Keep the Skyline

Medium

A district is a square grid heights of size n × n; heights[r][c] is the height of the tower in cell (r, c), and 0 means an empty lot. Seen from far away on any of the four sides, the district has a skyline: for every row (seen from the west or east) its tallest height, and for every column (seen from the north or south) its tallest height. Any tower, including an empty lot, may be raised by any non-negative amount, as long as the skyline from every side stays exactly the same. Return the largest possible total amount of raising.

Example 1

heights=[[2, 5], [4, 1]] → 5

Row maxima are 5 and 4, column maxima are 4 and 5. The 2 can grow to min(5, 4) = 4 (+2), the 1 to min(4, 5) = 4 (+3); the others are already at their limit. Total 5.

Example 2

heights=[[3, 3, 3], [3, 0, 3], [3, 3, 3]] → 3

Only the center tower can grow, up to 3.

Example 3

heights=[[0, 0], [0, 0]] → 0

Constraints

2 ≤ n ≤ 50
The grid is square: n rows of n numbers
0 ≤ heights[r][c] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Matrix

Similar problems

Best Binary Rows After Flips Medium Two Rows of Lamps Medium Rows Under the Diagonal Medium A Table From Its Totals Medium Biggest Block After a Column Shuffle Medium

Input

heights=[[2, 5], [4, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.