Easy & Detailed Approch 💡|| BFS 🔎 || All Languages 🔥
IntuitionThe problem involves finding the minimum height for each cell in a grid such that water cells have a height of 0, and land cells have a height that inc
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves finding the minimum height for each cell in a grid such that water cells have a height of `0`, and land cells have a height that increases as you move further away from water cells. This suggests using a Breadth-First Search (BFS) approach, where water cells are the starting points, and we propagate heights to neighboring land cells.

# Approach
<!-- Describe your approach to solving the problem. -->
1. **Initialization**: Create two matrices, `vis` to track visited cells and `hgt` to store the height of each cell.
2. **Queue Setup**: Push all water cells into a queue with an initial height of `0` and mark them as visited.
3. **BFS Traversal**: Use BFS to propagate the height to all neighboring land cells. For each cell processed, increment the height by `1` for each unvisited neighbor and push the neighbor into the queue.
4. **Direction Movement**: Utilize direction arrays to explore all four possible directions (up, right, down, left) from the current cell.
5. **Output**: Once the BFS completes, the `hgt` matrix contains the minimum heights for each cell.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
  The time complexity is $$O(m \times n)$$, where `m` is the number of rows and `n` is the number of columns. This is because each cell is visited exactly once.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
  The space complexity is $$O(m \times n)$$ due to the space used by the `vis` and `hgt` matrices and the queue, which can hold all cells in the worst case.


# Code
```cpp []
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size();
        int n = isWater[0].size();

        // Initialize visitation and height matrices
        vector<vector<int>> vis(m, vector<int>(n, 0));
        vector<vector<int>> hgt(m, vector<int>(n, 0));
        queue<pair<pair<int, int>, int>> q;

        // Add all water cells to the queue with height 0 and mark them as visited
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {  // Water cell
                    q.push({{i, j}, 0});   // Push coordinates and height into queue
                    hgt[i][j] = 0;         // Water cells have height 0
                    vis[i][j] = 1;         // Mark as visited
                }
            }
        }

        // Arrays to explore the four possible directions: up, right, down, left
        int row[4] = {-1, 0, +1, 0};
        int col[4] = {0, +1, 0, -1};

        // Process the queue using BFS
        while (!q.empty()) {
            auto value = q.front();
            int i = value.first.first;
            int j = value.first.second;
            int height = value.second;
            q.pop();
            
            // Update the height of the current cell
            hgt[i][j] = height;

            // Explore all four directions
            for (int k = 0; k < 4; k++) {
                int nrow = i + row[k];  // New row index
                int ncol = j + col[k];  // New column index
                
                // Check if the new cell is within bounds and not visited
                if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && vis[nrow][ncol] == 0) {
                    vis[nrow][ncol] = 1;   // Mark as visited
                    q.push({{nrow, ncol}, height + 1});  // Push new cell with incremented height
                }
            }
        }

        // Return the final height matrix
        return hgt;
    }
};

```
```javascript []
class Solution {
    highestPeak(isWater) {
        const m = isWater.length;
        const n = isWater[0].length;
        const vis = Array.from({ length: m }, () => Array(n).fill(0));
        const hgt = Array.from({ length: m }, () => Array(n).fill(0));
        const q = [];

        // Initialize the queue with water cells
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                if (isWater[i][j] === 1) { // Water cell
                    q.push([i, j, 0]);    // Add to queue with height 0
                    hgt[i][j] = 0;        // Set height to 0
                    vis[i][j] = 1;        // Mark as visited
                }
            }
        }

        // Directions for moving in the grid
        const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];

        // BFS traversal
        while (q.length > 0) {
            const [i, j, height] = q.shift();
            hgt[i][j] = height;

            // Explore all 4 directions
            for (const [di, dj] of directions) {
                const nrow = i + di;
                const ncol = j + dj;

                // Check bounds and visitation
                if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && vis[nrow][ncol] === 0) {
                    vis[nrow][ncol] = 1;
                    q.push([nrow, ncol, height + 1]); // Add to queue with incremented height
                }
            }
        }

        return hgt;
    }
}

```
```python []
from collections import deque

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        vis = [[0] * n for _ in range(m)]
        hgt = [[0] * n for _ in range(m)]
        q = deque()

        # Initialize the queue with water cells
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:  # Water cell
                    q.append((i, j, 0))  # Add to queue with height 0
                    hgt[i][j] = 0        # Set height to 0
                    vis[i][j] = 1        # Mark as visited

        # Directions for moving in the grid
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

        # BFS traversal
        while q:
            i, j, height = q.popleft()
            hgt[i][j] = height

            # Explore all 4 directions
            for di, dj in directions:
                nrow, ncol = i + di, j + dj

                # Check bounds and visitation
                if 0 <= nrow < m and 0 <= ncol < n and vis[nrow][ncol] == 0:
                    vis[nrow][ncol] = 1
                    q.append((nrow, ncol, height + 1))  # Add to queue with incremented height

        return hgt

```
```java []
import java.util.*;

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;

        int[][] vis = new int[m][n];
        int[][] hgt = new int[m][n];
        Queue<int[]> q = new LinkedList<>();

        // Initialize the queue with water cells
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) { // Water cell
                    q.offer(new int[]{i, j, 0}); // Add to queue with height 0
                    hgt[i][j] = 0;              // Set height to 0
                    vis[i][j] = 1;              // Mark as visited
                }
            }
        }

        // Directions for moving in the grid
        int[] row = {-1, 0, 1, 0};
        int[] col = {0, 1, 0, -1};

        // BFS traversal
        while (!q.isEmpty()) {
            int[] value = q.poll();
            int i = value[0], j = value[1], height = value[2];
            hgt[i][j] = height;

            // Explore all 4 directions
            for (int k = 0; k < 4; k++) {
                int nrow = i + row[k];
                int ncol = j + col[k];

                // Check bounds and visitation
                if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n && vis[nrow][ncol] == 0) {
                    vis[nrow][ncol] = 1;
                    q.offer(new int[]{nrow, ncol, height + 1}); // Add to queue with incremented height
                }
            }
        }

        return hgt;
    }
}

```


['Array', 'Depth-First Search', 'Breadth-First Search', 'Graph', 'Queue', 'Matrix', 'Binary Tree', 'C++', 'Java', 'Python3']