8

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?

12
  • Shouldn't the answer index 1? This would cause the next two buildings to collapse, and the second one (height 3) would cause the rest to collapse also. Also, what is "maximum devastation"? Is it the number of buildings that collapse, or their total height? Sep 25, 2013 at 11:31
  • No. Please read the question. H-1 buildings collapse and not H.
    – Sohaib
    Sep 25, 2013 at 11:32
  • @AnttiHuima if index is one, then only the 1st two buildings shall collapse. Sep 25, 2013 at 11:34
  • Maximum devastation means number of buildings or sum of heights? Sep 25, 2013 at 11:34
  • Maximum devastation means Number of buildings. Height only plays a role in the fall of buildings.
    – Sohaib
    Sep 25, 2013 at 11:36

5 Answers 5

10

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

1
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.

1
  • I realized the exact thing that only a height of 1 can stop the collapse. Could you please elaborate a little more.
    – Sohaib
    Sep 25, 2013 at 12:00
1
  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 ) )
2
  • What would be the complexity of this?
    – Sohaib
    Sep 25, 2013 at 11:54
  • Unfortunately complexity seems not very far from O(N^2), will need to make it more efficient Sep 25, 2013 at 11:59
0

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
1
  • Thanks but I never wanted the implementation. I explicitly mentioned algorithm.
    – Sohaib
    Sep 25, 2013 at 12:59
0

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;
}
5
  • 1
    No, this does not take subsequent collapses into consideration. Say we have the array [2,3,1,4,2,1,3,1], this will return 3 instead of 0, because collapsing of building #0 will cause #1 to collapse, which in turn will collapse #3, which in turn will collapse #6 resulting in total destruction.
    – Vesper
    Sep 25, 2013 at 12:02
  • I didn't consider subsequent collapses. So they apply? Sep 25, 2013 at 12:06
  • Yes, they do. "Collapse causes collapse" mean reiterate "collapse" for next buildings.
    – Vesper
    Sep 25, 2013 at 12:08
  • [1,3,1,2,4,3,1,2] should result in 1 as an answer, and your data mining says 0. See, collapsing the building at #0 won't result in any subsequent collapses, thus the damage at [0] should be 1, your subsequent-damage calculator says 8.
    – Vesper
    Sep 27, 2013 at 10:52
  • Most likely it's because your damage calculation gives 1 for 1-story building, which is then interpreted as 1 subsequent collapse, while there are 0. You should fix this. Undownvoted though.
    – Vesper
    Sep 27, 2013 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.