You are given an integer matrix isWater of size m x n that represents a map of land and water cells.
isWater[i][j] == 0, cell (i, j) is a land cell.isWater[i][j] == 1, cell (i, j) is a water cell.You must assign each cell a height in a way that follows these rules:
0.1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).Find an assignment of heights such that the maximum height in the matrix is maximized.
Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them.
Example 1:

Input: isWater = [[0,1],[0,0]] Output: [[1,0],[2,1]] Explanation: The image shows the assigned heights of each cell. The blue cell is the water cell, and the green cells are the land cells.
Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]] Output: [[1,1,0],[0,1,1],[1,2,2]] Explanation: A height of 2 is the maximum possible height of any assignment. Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.
Constraints:
m == isWater.lengthn == isWater[i].length1 <= m, n <= 1000isWater[i][j] is 0 or 1.Note: This question is the same as 542: https://leetcode.com/problems/01-matrix/
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
We need to figure out the height of each location in a map based on the heights of some known locations. The brute force approach will try setting a height for every location one by one, considering all possible height values. We will check if this height assignment is valid given the constraints.
Here's how the algorithm would work step-by-step:
def solve_map_brute_force(height_map, known_heights):
rows = len(height_map)
cols = len(height_map[0])
unknown_locations = []
for row_index in range(rows):
for col_index in range(cols):
if height_map[row_index][col_index] is None:
unknown_locations.append((row_index, col_index))
def is_valid(current_map):
for row_index in range(rows):
for col_index in range(cols):
if row_index > 0:
if current_map[row_index][col_index] is not None and current_map[row_index - 1][col_index] is not None and abs(current_map[row_index][col_index] - current_map[row_index - 1][col_index]) > 1:
return False
if col_index > 0:
if current_map[row_index][col_index] is not None and current_map[row_index][col_index - 1] is not None and abs(current_map[row_index][col_index] - current_map[row_index][col_index - 1]) > 1:
return False
return True
def solve(index, current_map):
if index == len(unknown_locations):
# All locations assigned, check if map is valid
if is_valid(current_map):
return current_map
else:
return None
row_index, col_index = unknown_locations[index]
for height in range(10):
# Trying every possible height at this location.
current_map[row_index][col_index] = height
valid_height = True
if row_index > 0 and current_map[row_index-1][col_index] is not None and abs(current_map[row_index][col_index] - current_map[row_index-1][col_index]) > 1:
valid_height = False
if col_index > 0 and current_map[row_index][col_index-1] is not None and abs(current_map[row_index][col_index] - current_map[row_index][col_index-1]) > 1:
valid_height = False
if valid_height:
result_map = solve(index + 1, current_map)
if result_map:
return result_map
# Reset the height for backtracking.
current_map[row_index][col_index] = None
return None
# Create a copy of the height map.
initial_map = [row[:] for row in height_map]
# Pre-fill known heights
for row_index in range(rows):
for col_index in range(cols):
if (row_index, col_index) in known_heights:
initial_map[row_index][col_index] = known_heights[(row_index, col_index)]
else:
initial_map[row_index][col_index] = None
# Recursively solve the map.
solution = solve(0, initial_map)
return solutionWe need to figure out the height of each location on a map based on given clues about differences in height between neighboring locations. The clever approach starts from a location we know the height of, and then figures out the heights of other locations by spreading out the height information from there.
Here's how the algorithm would work step-by-step:
def map_of_highest_peak(height_differences):
if not height_differences:
return []
rows = len(height_differences)
cols = len(height_differences[0])
heights = [[None] * cols for _ in range(rows)]
# Choose a starting point and assign it a height of 0.
start_row = 0
start_col = 0
heights[start_row][start_col] = 0
queue = [(start_row, start_col)]
while queue:
current_row, current_col = queue.pop(0)
# Iterate through neighbors to determine heights.
neighbors = [
# Up
(current_row - 1, current_col),
# Down
(current_row + 1, current_col),
# Left
(current_row, current_col - 1),
# Right
(current_row, current_col + 1)
]
for neighbor_row, neighbor_col in neighbors:
if 0 <= neighbor_row < rows and 0 <= neighbor_col < cols and heights[neighbor_row][neighbor_col] is None:
# Determine height of neighboring cell
if neighbor_row < current_row:
heights[neighbor_row][neighbor_col] = heights[current_row][current_col] - height_differences[neighbor_row][current_col]
elif neighbor_row > current_row:
heights[neighbor_row][neighbor_col] = heights[current_row][current_col] + height_differences[current_row][current_col]
elif neighbor_col < current_col:
heights[neighbor_row][neighbor_col] = heights[current_row][current_col] - height_differences[current_row][neighbor_col]
else:
heights[neighbor_row][neighbor_col] = heights[current_row][current_col] + height_differences[current_row][current_col - 1]
queue.append((neighbor_row, neighbor_col))
# Shift all heights to ensure the smallest height is 0.
min_height = min(min(row) for row in heights)
# Ensure no negative heights exist
for row in range(rows):
for col in range(cols):
heights[row][col] -= min_height
return heights| Case | How to Handle |
|---|---|
| Null or empty height map | Return an empty matrix or throw an IllegalArgumentException as no valid peak map can be constructed. |
| Height map with only one cell | Return a 1x1 matrix with value 0, as it's the only possible solution. |
| Height map with all zero heights specified | Start the BFS from cells with specified height zero and proceed outwards. |
| Integer overflow during height calculation (if heights are derived from coordinates) | Use a data type that can accommodate larger values, such as long, or perform modular arithmetic to prevent overflow. |
| Large map dimensions that may cause memory issues | Ensure the data structures used (queue, result matrix) are memory-efficient, potentially processing in chunks if needed for extremely large maps. |
| Negative initial heights are provided. | Ensure initial height values are handled correctly, treating them as minimum heights in the water flow simulation. |
| Cells with the same initial height are adjacent to each other. | The algorithm should correctly handle areas with the same known height, expanding outwards in a consistent manner. |
| The provided input grid is not rectangular. | The algorithm should either throw an exception, or gracefully handle by considering only rectangular portions when determining neighbors. |