Map of Highest Peak

Intuition

Understand the Problem

First of all, let's get the description of the problem clear.

The input of this problem is a 2-dimension array representing a matrix and whether each cell in the matrix contains water. If a cell has water, then it's height is zero.
The limitation of the problem is that the height of each two of adjacent cells (up, down, left, right) should be 1 or 0.
The output of this problem is a matrix representing height of each cell, where the maximum height of of cells is maximized.

Abstruct Using Data Structure

The input is actually a graph, where each cell is a point in the graph. And each cell is connected to at most 4 cells (less than 4 if the cell is on the edge of the matrix). So we can try to solve this problem using some graph algorithms like BFS, DFS or even some advanced algorithms like DJI.

Idea

Think from 3 aspects.

Let's say we have 2 adjancent points (cells) p1 and p2, from the limitation of this problem, if p1 has height h1, then the maximum height of p2 is h1 + 1.
If we already know the points with maximum height less than h, then all points which is unknown and is adjacent to points with height h can be assigned to at most h + 1.
If we already know the points with maximum height h, then that means we already assigned all cells which should have height less than h.

So we can assign height to each points by the following order. First, assign cells whose height can be 1, then 2, 3, etc.

About Code

The solution is almost a standard breadth-first search (BFS). First, we initialize a queue where all elements in the queue has height 0. Then we pop points from the queue. Each time if we find a adjacent point which is undefined, we put it into the queue. This keeps that the prior point in the queue always has lower or equal height than later points.

Note:

Status is_visited for each point is stored in the height matrix as -1.

Items in the queue is a tuple with 3 values, (<height, x_index, y_index>).

queue.Queue is a python internal library to support basic first-in first-out (FIFO) queue queue.

Solution


import queue


class Solution:
    def highestPeak(self, isWater):
        rows = len(isWater)
        cols = len(isWater[0])
        height = [[-1] * cols for _ in range(rows)]

        handle_later = queue.Queue()
        for i in range(rows):
            for j in range(cols):
                if isWater[i][j]:
                    handle_later.put((0, i, j))
                    height[i][j] = 0

        while not handle_later.empty():
            h, i, j = handle_later.get()
            for neighborI, neighborJ in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
                if neighborI < 0 or neighborI >= rows or neighborJ < 0 or neighborJ >= cols:
                    continue
                if height[neighborI][neighborJ] >= 0:
                    continue
                height[neighborI][neighborJ] = h + 1
                handle_later.put((h + 1, neighborI, neighborJ))
        return height