✅ Easy to Understand | Breadth-First Search | Java | Google | Detailed Video Explanation🔥
IntuitionThe problem involves assigning heights to land cells such that the height of each cell is the minimum distance to the nearest water cell. The most natu
# Intuition
The problem involves assigning heights to land cells such that the height of each cell is the minimum distance to the nearest water cell. The most natural way to solve this is by treating the water cells as starting points and performing a multi-source breadth-first search (BFS). BFS ensures that the shortest path to water is calculated for every cell efficiently.

# Approach
1. **Initialization:**
   - Create a queue to perform BFS.
   - Traverse the grid to find all water cells (`isWater[i][j] == 1`). Set their heights to `0` in the result grid and mark them as visited. Add these water cells to the queue.

2. **Breadth-First Search (BFS):**
   - Start from all water cells simultaneously, processing each level of cells incrementally.
   - For each cell, explore its four neighbors (up, down, left, right).
   - If a neighbor is within bounds, unvisited, and land, calculate its height as `current cell height + 1`, mark it as visited, and add it to the queue for further processing.

3. **Termination:**
   - Continue BFS until all reachable cells are processed. The height of each cell is updated in the result grid as the BFS progresses.

4. **Return Result:**
   - The result grid contains the height of all cells such that each cell's height is the shortest distance to a water cell.

# Complexity
- **Time complexity:**
  $$O(m \times n)$$  
  Every cell in the grid is visited exactly once, and all its neighbors are processed. The total work is proportional to the number of cells in the grid.

- **Space complexity:**
  $$O(m \times n)$$  
  The space required for the queue, visited array, and result grid is proportional to the number of cells in the grid.


# Code
```java []
class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length; // Number of rows in the grid
        int n = isWater[0].length; // Number of columns in the grid
        int height = 0; // Height to be assigned to each cell level by level

        // Directions for moving up, down, left, and right
        int[][] dir = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        int[][] ans = new int[m][n]; // Result grid to store the height of each cell
        boolean[][] visited = new boolean[m][n]; // To keep track of visited cells

        // Queue for BFS (breadth-first search)
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    // If the cell is water, set it as the starting point with height 0
                    q.offer(new int[] { i, j });
                    visited[i][j] = true; // Mark water cells as visited
                }
            }
        }

        // BFS to calculate heights for all cells
        while (!q.isEmpty()) {
            int len = q.size(); // Number of cells to process at the current height
            while (len-- > 0) {
                int[] curr = q.poll(); // Get the current cell
                int i = curr[0];
                int j = curr[1];
                ans[i][j] = height; // Assign the current height to the cell

                // Check all four neighboring cells
                for (int[] d : dir) {
                    int ni = i + d[0]; // Neighbor row index
                    int nj = j + d[1]; // Neighbor column index
                    // If the neighbor is within bounds and not visited
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                        q.offer(new int[] { ni, nj }); // Add neighbor to the queue
                        visited[ni][nj] = true; // Mark the neighbor as visited
                    }
                }
            }
            height++; // Increment the height for the next level of cells
        }
        return ans; // Return the result grid
    }
}

```




LeetCode 1765 Map of Highest Peak | BFS | Google
https://youtu.be/qiUhyPCqIcU
['Array', 'Breadth-First Search', 'Matrix', 'Java']