Google | Onsite | Highest Peak
7770

Given a 2D boolean array where true represents water and false represents land, generate a grid with highest possible peak. Rules are:

  1. the height of any water cell is 0.
  2. the height of any land cell cannot differ for more than one from any of the neighbouring (sharing one edge) cells.

Example:

Input:
[[T, F, T],
 [F, F, F],
 [F, F, F]]

One possible grid is
[[0, 0, 0],
 [1, 0, 1],
 [2, 1, 2]]

And grid 
[[0, 2, 0], 
 [0, 0, 0],
 [0, 0, 0]]
is not possible (2 differs more than 1 from the neighbouring cell)

Output:  
[[0, 1, 0],
 [1, 2, 1],
 [2, 3, 2]]
where the highest peak is 3.

Follow-up:
What if we want to add secondary optimization goal: maximize the amount of cells with the height of 0 while keeping max peak height.

Comments (16)