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

In Java, without considering subsequent collapses:

public static int collapse(int[] buildings) {
    int i, maxDamage, index, currentDamage;
    // do not consider the last building, it will cause only its own fall
    maxDamage = 1;
    index = buildings.length - 1;
    for(i = buildings.length - 1; i >= 0; i--) {
        // update maximum damage as the mimimum value between the building[i] (the height of the building at index i) and the remaining number of elements from i to the end of the array
        currentDamage = Math.min(buildings[i], buildings.length - i);
        System.out.println(currentDamage);
        if(currentDamage > maxDamage) {
            maxDamage = currentDamage;
            index = i;
        }
    }
    return index;
}

My final solution is different from the accepted one, which by the way I didn't fully understand. The idea is to count starting from the rightmost position the number of buildings that the current index will collapse.

index:  7  6  5  4  3  2  1  0
height: 1  3  1  2  4  1  3  2
damage: 1  2  1  2  4  1  3  2

Then I just make a cumulative sum, starting from the rightmost position again. I add to the number of buildings the current position collapses the number of buildings that were collapsed staring from the next building to the right that didn't collapse until the end.

index:  7  6  5  4  3  2  1  0
height: 1  3  1  2  4  1  3  2
damage: 1  2  1  2  5  1  7  8

In the end, I just return the index with the maximum damage.

This solution runs in O(n) but uses an extra O(n) space.

The next code is the complete version (also works for subsequent collapses):

public static int collapse(int[] buildings) {
    int i, maxIndex, max;
    int damage[] = new int[buildings.length];
    for(i = buildings.length - 1; i >= 0; i--) {
        // compute damage for each position
        damage[i] = Math.min(buildings[i], buildings.length - i);
    }
    for(i = buildings.length - 1; i >= 0; i--) {
        // update total accumulated damage for each position
        if(damage[i] > 1) {
            if(damage[i] + i - 1 < buildings.length && i != (i + damage[i] - 1) ) {
                damage[i] += damage[i + damage[i] - 1] - 1;
            }
        }
    }
    max = damage[0];
    maxIndex = 0;
    for(i = 1; i < buildings.length; i++) {
        // find the maximum damage
        if(damage[i] > max) {
            max = damage[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}

Answer 2

Same approach as @Karoly's answer. In ruby:

def find_max_damage_index(buildings)

  max_damage = 0
  max_start_index = nil

  current_start_index = nil
  current_h = 0
  current_damage = 0

  buildings.each_with_index{|h,i|
    if current_h == 0 #end of batch
      if current_damage > max_damage
        max_damage = current_damage
        max_start_index = current_start_index
      end
      #start new batch
      current_h = h
      current_damage = 1
      current_start_index = i
    else
      current_h = h if h > current_h
      current_damage += 1
    end
    current_h -= 1
  }
  #last batch
  if current_damage > max_damage
    max_damage = current_damage
    max_start_index = current_start_index
  end

  return max_start_index
end

Answer 3

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 4

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 5

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 ) )