Maximum Devastation to be caused if a building with height h causes all h-1 buildings to its right to collapse

Question

In a recent interview question I got the following problem.

In a particular city we have a row of buildings with varying heights. The collapse of a building with height h causes the next h-1 buildings on its right to collapse too. The height of the buildings can be between 1 and 5000. Given the heights of all the buildings (arranged from left to right ie; for leftmost building index=1 and for rightmost building index=N) we needed to find out the index of the building which would cause the maximum devastation.

For example:

Input: Number of buildings : 6

Height of Buildings: 2 1 3 3 1 6

Answer should be building at the index 3

The solution I tried was using the brute force technique with a complexity of O(N^2). What I did was for each building in the list I found out the number of buildings that it would destroy.

Could a better solution for this question be constructed?

Answer 1

Simply go from the left, collapse the first building, and calculate how much total(*) damage it did.

Do this again and again from the very next building (which hasn't collapsed).

From these, pick the maximum.

Complexity: O(n).

This greedy algorithm works because the whole process is a chain reaction, if building A forces the collapse of B, then you cannot achieve better score starting from B.

(*) You can do this by maintaining one counter which stores how many buildings to the right should be collapsed. counter = max(counter - 1, height of next building).

Answer 2

some areas of the city function as "firewalls" - collapse stops at that point. a little thought shows that these are sections to the left of a value of 1 where height increases (to the left) no more than once per step (if you can have 0 heights that complicates things very slightly).

and the highest scoring region must start just after a firewall (since if it didn't there would be a higher region just to the left).

so scan from the right, finding these firewalls, and then find which section to the right of a firewall has the largest damage. this is O(n) because it's just linear scans (once from right to left and then once for each section, with no overlap).

actually, Karoly's answer is equivalent and simpler to implement.

Answer 3

1. Start with rightmost index.
2. The last building shall cause a devastation value of 1.
3. Iterate leftwards.

Something like (devastation from building i)

D[i] = 1 + min( N-i, max( index[i]-1, 0+D[i+1],1+D[i+2],... to index[i]-1 terms ) )