Problem Description

You have a grid representing a map with land and water cells. The grid isWater has dimensions m x n where:

• isWater[i][j] = 0 means cell (i, j) is land
• isWater[i][j] = 1 means cell (i, j) is water

Your task is to assign a height value to each cell following these rules:

1. All heights must be non-negative integers
2. Water cells must have height 0
3. Adjacent cells (horizontally or vertically connected) can differ in height by at most 1

The goal is to maximize the highest peak possible on the map while satisfying all constraints.

The solution uses a multi-source BFS approach. It starts by identifying all water cells as sources with height 0 and adds them to a queue. Then it performs BFS to assign heights to land cells layer by layer. Each land cell gets assigned a height that is 1 more than the minimum height of its already-processed neighbors. This ensures the height difference constraint is satisfied while maximizing the overall heights.

The algorithm works by:

1. Initializing all cells to -1 (unvisited)
2. Setting all water cells to height 0 and adding them to the queue
3. Processing cells level by level using BFS
4. For each cell, checking its 4 adjacent neighbors
5. If a neighbor hasn't been visited, assigning it a height of current cell's height + 1

This approach guarantees that each land cell gets the maximum possible height while maintaining the constraint that adjacent cells differ by at most 1.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node and adjacent cells (up, down, left, right) are connected by edges. We need to traverse this graph structure.

Is it a tree?

• No: The grid structure is not a tree. It's a graph where cells can have multiple paths between them and cycles can exist.

Is the problem related to directed acyclic graphs?

• No: The grid is essentially an undirected graph where adjacency is bidirectional.

Is the problem related to shortest paths?

• Yes: We need to find the minimum distance from each land cell to the nearest water cell. The height of each land cell is essentially its shortest distance to water.

Is the graph Weighted?

• No: Each step between adjacent cells has the same "cost" of 1 (height difference of 1), making this an unweighted graph problem.

BFS

• Yes: For unweighted shortest path problems, BFS is the optimal choice.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for this problem. This makes perfect sense because:

1. We need to find the shortest distance from each land cell to the nearest water cell
2. The graph is unweighted (each step increases height by exactly 1)
3. BFS naturally processes cells level by level, ensuring we assign the minimum possible height to each cell while maintaining the constraint that adjacent cells differ by at most 1
4. Using multi-source BFS (starting from all water cells simultaneously) efficiently computes the shortest distance from each cell to any water source

Intuition

The key insight is recognizing that this problem is fundamentally about finding distances. Each land cell's height represents its minimum distance to the nearest water source.

Think of water spreading outward from all water cells simultaneously. The water "rises" by 1 unit with each step it takes away from the source. This naturally creates the height map we're looking for - cells closer to water have lower heights, and cells farther away have higher heights.

Why does this work? Consider the constraints:

• Water cells must have height 0 (our starting points)
• Adjacent cells can differ by at most 1 in height
• We want to maximize heights

If we imagine pouring water that rises level by level, the first ring of land cells around water would get height 1, the next ring would get height 2, and so on. This ensures:

1. We satisfy the adjacency constraint (each level differs by exactly 1)
2. We maximize heights (each cell gets the highest possible value given its distance to water)

The multi-source BFS approach naturally implements this "water spreading" idea. By starting from all water cells simultaneously and processing cells level by level, we guarantee that:

• Each cell is reached first via its shortest path to water
• The height assigned equals this shortest distance
• No cell can have a higher height without violating the adjacency constraint

This is why BFS is perfect here - it explores the graph level by level, ensuring we find the minimum distance (and thus assign the correct height) for each cell in the optimal order.

Learn more about Breadth-First Search patterns.

Solution Approach

The implementation uses a multi-source BFS with a queue to efficiently assign heights to all cells:

1. Initialization Phase:

• Create a result matrix ans initialized with -1 to mark unvisited cells
• Use a deque (double-ended queue) for BFS traversal
• Scan through the entire grid to find all water cells
• For each water cell at position (i, j), set ans[i][j] = 0 and add (i, j) to the queue

2. BFS Traversal:

• Process cells level by level from the queue
• For each cell (i, j) dequeued:
  • Check all 4 adjacent cells (up, down, left, right)
  • The pairwise((-1, 0, 1, 0, -1)) cleverly generates direction pairs: (-1, 0), (0, 1), (1, 0), (0, -1)
  • For each adjacent cell (x, y):
    • Check if it's within bounds: 0 <= x < m and 0 <= y < n
    • Check if it's unvisited: ans[x][y] == -1
    • If both conditions are met:
      • Assign height: ans[x][y] = ans[i][j] + 1
      • Add (x, y) to the queue for future processing

3. Key Implementation Details:

• Using -1 as a marker for unvisited cells serves dual purpose: tracking visited status and avoiding revisiting
• The pairwise function with (-1, 0, 1, 0, -1) is a compact way to generate the 4 directional offsets
• BFS guarantees that when we first reach a cell, we've found its shortest distance to water
• The queue ensures we process cells in order of their distance from water (level by level)

Time Complexity: O(m × n) where we visit each cell exactly once Space Complexity: O(m × n) for the result matrix and at most O(m × n) for the queue in worst case

This approach elegantly solves the problem by treating it as a shortest path problem in an unweighted graph, where BFS naturally gives us the optimal solution.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a 3×4 grid where 0 represents land and 1 represents water:

isWater = [[0, 0, 1, 0],
           [0, 0, 0, 0],
           [1, 0, 0, 0]]

Step 1: Initialization

• Create result matrix ans filled with -1 (unvisited)
• Find all water cells and set them to height 0
• Add water cells to queue

ans = [[-1, -1,  0, -1],    Queue: [(0,2), (2,0)]
       [-1, -1, -1, -1],    
       [ 0, -1, -1, -1]]

Step 2: Process first level (distance 1 from water)

• Dequeue (0,2): Check its 4 neighbors
  • (0,1): unvisited, set height = 0 + 1 = 1, add to queue
  • (0,3): unvisited, set height = 0 + 1 = 1, add to queue
  • (1,2): unvisited, set height = 0 + 1 = 1, add to queue
• Dequeue (2,0): Check its 4 neighbors
  • (2,1): unvisited, set height = 0 + 1 = 1, add to queue
  • (1,0): unvisited, set height = 0 + 1 = 1, add to queue

ans = [[-1,  1,  0,  1],    Queue: [(0,1), (0,3), (1,2), (2,1), (1,0)]
       [ 1, -1,  1, -1],    
       [ 0,  1, -1, -1]]

Step 3: Process second level (distance 2 from water)

• Dequeue and process cells with height 1
• Each unvisited neighbor gets height = 1 + 1 = 2

After processing (0,1), (0,3), (1,2), (2,1), (1,0):

ans = [[2,  1,  0,  1],    Queue: [(0,0), (1,1), (1,3), (2,2)]
       [1,  2,  1,  2],    
       [0,  1,  2, -1]]

Step 4: Process third level (distance 3 from water)

• Process remaining cells with height 2
• Cell (2,3) gets height = 2 + 1 = 3

Final result:

ans = [[2, 1, 0, 1],
       [1, 2, 1, 2],
       [0, 1, 2, 3]]

The maximum height achieved is 3 at position (2,3), which is the land cell farthest from any water source. Notice how each cell's height equals its shortest distance to water, and adjacent cells differ by at most 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid.

• The initial nested loop to find all water cells and add them to the queue takes O(m * n) time as it visits every cell once.
• The BFS traversal processes each cell exactly once. When a cell is processed, it's marked with a value (no longer -1), and only cells with value -1 are added to the queue. Therefore, each of the m * n cells is added to and removed from the queue at most once.
• For each cell processed, we check at most 4 neighbors using the pairwise function, which is O(1) operation per cell.
• Total time: O(m * n) + O(m * n) * O(1) = O(m * n)

Space Complexity: O(m * n)

• The answer matrix ans requires O(m * n) space to store the height values for all cells.
• The queue q can contain at most O(m * n) elements in the worst case (though typically much less - at most all water cells initially, then frontier cells during BFS).
• The pairwise operation creates temporary tuples but uses O(1) additional space.
• Total space: O(m * n) + O(m * n) = O(m * n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using DFS Instead of BFS

A common mistake is attempting to solve this problem with DFS, which doesn't guarantee the shortest path to water cells. DFS might assign suboptimal heights because it explores one path deeply before backtracking.

Why it fails: DFS could reach a land cell through a longer path first, assigning it a higher value than necessary. Later, when a shorter path is found, the cell is already visited and won't be updated.

Solution: Always use BFS for shortest path problems in unweighted graphs. BFS explores level by level, ensuring the first time we reach a cell is via the shortest path.

2. Not Using Multi-Source BFS

Some might try to run BFS from each water cell individually, which leads to incorrect results or inefficiency.

Why it fails: Running separate BFS from each water source would require complex logic to determine which water source should "win" for each land cell, and would have O(m × n × k) time complexity where k is the number of water cells.

Solution: Initialize all water cells in the queue simultaneously. This treats all water cells as starting points at distance 0, naturally computing the minimum distance to any water cell.

3. Incorrect Visited Cell Tracking

Using a separate boolean matrix for tracking visited cells or checking isWater array instead of the result matrix.

Why it fails: This adds unnecessary space complexity and can lead to synchronization issues between the visited status and height assignments.

Solution: Use the result matrix itself with -1 as the unvisited marker. This serves dual purpose: tracking visited status and storing the final heights.

4. Processing the Same Cell Multiple Times

Forgetting to mark cells as visited immediately when adding them to the queue.

# WRONG: Mark as visited when dequeuing
while queue:
    row, col = queue.popleft()
    if heights[row][col] != -1:  # Already visited
        continue
    heights[row][col] = some_value  # Too late!
  
# CORRECT: Mark as visited when enqueuing
if heights[next_row][next_col] == -1:
    heights[next_row][next_col] = heights[current_row][current_col] + 1
    queue.append((next_row, next_col))

Why it fails: The same cell could be added to the queue multiple times from different neighbors, leading to redundant processing and potentially incorrect results.

Solution: Always mark the cell as visited (assign its height) immediately when adding it to the queue, not when dequeuing it.