🔥 Multiple Approach - BFS/Greedy Simple Detailed Explanation
IntuitionThe problem requires finding the minimum distance of each cell to the nearest water cell in a grid. A breadth-first search (BFS) approach is well-suite
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires finding the minimum distance of each cell to the nearest water cell in a grid. A breadth-first search (BFS) approach is well-suited for this because it naturally explores the shortest path level by level. Starting from all water cells, we can propagate distances to surrounding land cells.
# Approach
<!-- Describe your approach to solving the problem. -->
- Initialization:
Create a queue to store coordinates of all water cells (isWater[i][j] == 1) as starting points.
Initialize a 2D vector ans with dimensions equal to the input grid, setting all values to -1 to mark unvisited cells.

- Breadth-First Search (BFS):
Start BFS from all water cells simultaneously. Push them into the queue and mark their distance as 0 in the ans grid.
For each cell in the queue, explore its four neighbors (up, down, left, right). If a neighbor is unvisited (ans[new_x][new_y] == -1), calculate its distance as 1 + ans[x][y] and push it into the queue.
Edge Cases:

- If the grid contains only water cells, the result will be all zeros.
- If the grid contains only land cells, the BFS initializes no water cells, and the result will remain as it is.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
    O(n×m)
    Each cell is processed once when added to the queue and each neighbor is checked.

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
    O(n×m)
    Space is used for the ans grid and the queue storing at most all cells in the grid.

# Approach - 1
# Code
```cpp []
class Solution {
    void bfs(vector<vector<int>> &visited,vector<vector<int>> &isWater,vector<vector<int>> &ans,queue<pair<int,int>> &q){
        // visited[i][j]=1;
        int n=isWater.size(),m=isWater[0].size();
        vector<int> newx={0,1,0,-1};
        vector<int> newy={-1,0,1,0};
        // q.push({i,j});
        while(!q.empty()){
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            for(int k=0;k<4;k++){
                int new_x=x+newx[k];
                int new_y=y+newy[k];
                if(new_x>=0 and new_x<n and new_y>=0 and new_y<m and ans[new_x][new_y]==-1){
                    ans[new_x][new_y]=1+ans[x][y];
                    visited[new_x][new_y]=1;
                    q.push({new_x,new_y});
                }
            }
        }
    }
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int n=isWater.size(),m=isWater[0].size();
        vector<vector<int>> visited(n,vector<int> (m,0));
        vector<vector<int>> ans(n,vector<int> (m,-1));
        queue<pair<int,int>> q;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(isWater[i][j]==1){
                    ans[i][j]=0;
                    q.push({i,j});
                }
            }
        }
        bfs(visited,isWater,ans,q);
        return ans;
    }
};

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

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int n = isWater.length, m = isWater[0].length;
        int[][] ans = new int[n][m];
        for (int[] row : ans) Arrays.fill(row, -1); // Initialize the ans array with -1
        Queue<int[]> q = new LinkedList<>();

        // Add all water cells to the queue
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (isWater[i][j] == 1) {
                    ans[i][j] = 0; // Water cells have height 0
                    q.add(new int[]{i, j});
                }
            }
        }

        int[] dx = {0, 1, 0, -1};
        int[] dy = {-1, 0, 1, 0};

        // Perform BFS
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int x = cell[0], y = cell[1];
            for (int k = 0; k < 4; k++) {
                int newX = x + dx[k];
                int newY = y + dy[k];
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && ans[newX][newY] == -1) {
                    ans[newX][newY] = ans[x][y] + 1;
                    q.add(new int[]{newX, newY});
                }
            }
        }

        return ans;
    }
}
```
``` python []
from collections import deque

class Solution:
    def highestPeak(self, isWater: list[list[int]]) -> list[list[int]]:
        n, m = len(isWater), len(isWater[0])
        ans = [[-1] * m for _ in range(n)]  # Initialize the answer grid with -1
        q = deque()

        # Add all water cells to the queue
        for i in range(n):
            for j in range(m):
                if isWater[i][j] == 1:
                    ans[i][j] = 0  # Water cells have height 0
                    q.append((i, j))

        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # Perform BFS
        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                newX, newY = x + dx, y + dy
                if 0 <= newX < n and 0 <= newY < m and ans[newX][newY] == -1:
                    ans[newX][newY] = ans[x][y] + 1
                    q.append((newX, newY))

        return ans

```
# Approach - 2

# Approach
- Initialization:
    Create a height grid initialized to a large value (R + C, where R and C are the grid's dimensions).
    Set water cells (isWater[i][j] == 1) to height 0.

- Two-Pass Propagation:
    First Pass (Top-Left to Bottom-Right):
    Update each cell's height based on its top and left neighbors.
    Second Pass (Bottom-Right to Top-Left):
    Update each cell's height based on its bottom and right neighbors.

- Key Idea:
    By sweeping twice through the grid, each cell's height gets the minimum possible value as distances from all directions are considered.

# Code
``` cpp []
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int R = isWater.size();
        int C = isWater[0].size();
        vector<vector<int>> height(R, vector<int>(C, R + C));

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                } else {
                    if (i > 0) 
                        height[i][j] = min(height[i][j], height[i - 1][j] + 1);
                    if (j > 0) 
                        height[i][j] = min(height[i][j], height[i][j - 1] + 1);
                }
            }
        }

        for (int i = R - 1; i >= 0; i--) {
            for (int j = C - 1; j >= 0; j--) {
                if (i < R - 1) 
                    height[i][j] = min(height[i][j], height[i + 1][j] + 1);
                if (j < C - 1) 
                    height[i][j] = min(height[i][j], height[i][j + 1] + 1);
            }
        }

        return height;
    }
};
```
``` python []
class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        R, C = len(isWater), len(isWater[0])
        height = [[R + C] * C for _ in range(R)]
        
        for i in range(R):
            for j in range(C):
                if isWater[i][j] == 1:
                    height[i][j] = 0
                else:
                    if i > 0:
                        height[i][j] = min(height[i][j], height[i - 1][j] + 1)
                    if j > 0:
                        height[i][j] = min(height[i][j], height[i][j - 1] + 1)
        
        for i in range(R - 1, -1, -1):
            for j in range(C - 1, -1, -1):
                if i < R - 1:
                    height[i][j] = min(height[i][j], height[i + 1][j] + 1)
                if j < C - 1:
                    height[i][j] = min(height[i][j], height[i][j + 1] + 1)
        
        return height
```
``` java []
class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int R = isWater.length;
        int C = isWater[0].length;
        int[][] height = new int[R][C];
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                height[i][j] = R + C;
            }
        }
        
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                } else {
                    if (i > 0) 
                        height[i][j] = Math.min(height[i][j], height[i - 1][j] + 1);
                    if (j > 0) 
                        height[i][j] = Math.min(height[i][j], height[i][j - 1] + 1);
                }
            }
        }
        
        for (int i = R - 1; i >= 0; i--) {
            for (int j = C - 1; j >= 0; j--) {
                if (i < R - 1) 
                    height[i][j] = Math.min(height[i][j], height[i + 1][j] + 1);
                if (j < C - 1) 
                    height[i][j] = Math.min(height[i][j], height[i][j + 1] + 1);
            }
        }
        
        return height;
    }
}

```
['Array', 'Dynamic Programming', 'Greedy', 'Breadth-First Search', 'Graph', 'Matrix', 'Python', 'C++', 'Java']