In order to solve this problem, we need to think of these heights as minimum distances from the closest water tiles. The most intuitive way of doing this is starting a level-by-level, i.e. breadth-first search from the given sea tiles. Initially, we also set the non-sea tiles to -1 to represent that they are not assigned yet. We only assign a tile a height if its height is unassigned so that we don't reassign greater heights.
Appraoch 2-Cardinal Comparison:
In theory, the BFS approach should be fast but the data structures required for it are always slow in implementation. We can solve this problem by only using arrays. Before understanding how this is done, one can refer to #295. If we given just a line of tiles, the closest water tile would have been either the closest left one or the closest right. Hence, for every single individual row in the map, we can calculate these distances. Since the map is naturally 2D, we can also apply this strategy for every single column. In each column, the distance from water can just be the vertical distance to some other tile plus the height of that tile, so we calculate the Manhattan Distance from corresponding water tiles indirectly. We always pick the minimum and eventually set up the complete height map.
Problem: https://leetcode.com/problems/map-of-highest-peak/
Appraoch 1-BFS
In order to solve this problem, we need to think of these heights as minimum distances from the closest water tiles. The most intuitive way of doing this is starting a level-by-level, i.e. breadth-first search from the given sea tiles. Initially, we also set the non-sea tiles to -1 to represent that they are not assigned yet. We only assign a tile a height if its height is unassigned so that we don't reassign greater heights.
Appraoch 2-Cardinal Comparison:
In theory, the BFS approach should be fast but the data structures required for it are always slow in implementation. We can solve this problem by only using arrays. Before understanding how this is done, one can refer to #295. If we given just a line of tiles, the closest water tile would have been either the closest left one or the closest right. Hence, for every single individual row in the map, we can calculate these distances. Since the map is naturally 2D, we can also apply this strategy for every single column. In each column, the distance from water can just be the vertical distance to some other tile plus the height of that tile, so we calculate the Manhattan Distance from corresponding water tiles indirectly. We always pick the minimum and eventually set up the complete height map.