Beats 98.29% | Without BFS | With BFS | Matrix | Solution for LeetCode#1765
IntuitionThe problem asks to assign heights to cells in a grid, where water cells have height 0 and land cells have positive heights. The height of each land ce
![image.png](https://assets.leetcode.com/users/images/f000070a-ed43-46e8-8494-abe3e24155a5_1737520078.8155313.png)
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem asks to assign heights to cells in a grid, where water cells have height 0 and land cells have positive heights. The height of each land cell should be the minimum distance to the nearest water cell. This suggests using a breadth-first search (BFS) approach starting from all water cells simultaneously.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Initialize a matrix with the same dimensions as the input, setting water cells to 0 and land cells to -1 (unvisited).
2. Create a queue and add all water cell coordinates to it.
3. Perform BFS:
	- For each cell in the queue, check its four adjacent cells.
	- If an adjacent cell is within bounds and unvisited (height -1), set its height to the current cell's height + 1.
	- Add the newly visited cell to the queue.
4. Continue until the queue is empty, which means all cells have been assigned a height.

# Complexity
- Time complexity: O(m * n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(m * n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code Option-01
![image.png](https://assets.leetcode.com/users/images/d163bb3e-5d14-40b0-a968-de4629b3b70a_1737505761.8629253.png)

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

        // Initialize result matrix with same dimensions as input
        int[][] matrix=new int[m][n];

        // Queue to perform BFS
        Queue<int[]> que=new LinkedList<>();


        // Initialize matrix and queue
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(isWater[i][j]==1){
                    // Water cells have height 0 and are added to queue
                    que.add(new int[]{i,j});
                }
                else{
                    // Mark land cells as unvisited (-1)
                    matrix[i][j]=-1;
                }
            }
        }


        // Possible directions: right, left, down, up
        int[][] directions={ {0,1}, {0,-1}, {1,0}, {-1,0} };

        //BFS Traverse
        while(!que.isEmpty()){
            int[] arr=que.poll();
            int r=arr[0];
            int c=arr[1];

            // Check all adjacent cells
            for(int[] dir:directions){
                int nr=r+dir[0];
                int nc=c+dir[1];

                // If adjacent cell is within boundary and unvisited
                if(nr>=0 && nr<m && nc>=0 && nc<n && matrix[nr][nc]==-1){
                    // Set height to 1 more than current cell
                    matrix[nr][nc]=matrix[r][c]+1;  

                    // Add to queue for further exploration
                    que.add(new int[]{nr,nc});      
                } 
            }
        }

        return matrix;
    }
}
```
```python []
class Solution(object):
    def highestPeak(self, isWater):
        """
        :type isWater: List[List[int]]
        :rtype: List[List[int]]
        """
        m, n = len(isWater), len(isWater[0])
        # Initialize result matrix with same dimensions as input
        matrix = [[-1] * n for _ in range(m)]

        # Queue to perform BFS
        que = deque()

        # Initialize matrix and queue
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    # Water cells have height 0 and are added to queue
                    que.append((i, j, 0))
                    matrix[i][j] = 0

        # Possible directions: right, left, down, up
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        # BFS Traversal
        while que:
            r, c, height = que.popleft()

            # Check all adjacent cells
            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # If adjacent cell is within bounds and unvisited
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] == -1:
                    # Set height to 1 more than current cell
                    matrix[nr][nc] = height + 1
                    # Add to queue for further exploration
                    que.append((nr, nc, height + 1))

        # Return the completed height map
        return matrix
```


# Code Option-02: No BFS
![image.png](https://assets.leetcode.com/users/images/f000070a-ed43-46e8-8494-abe3e24155a5_1737520078.8155313.png)

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

        // Initialize result matrix with same dimensions as input
        int[][] matrix=new int[m][n];

        // Initialize the matrix 
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(isWater[i][j]!=1){                                
                    // Mark land cells as MAX_VALUE
                    matrix[i][j]=10000000;
                }
            }
        }


        int neighborValue=10000000; 

        // Forward Pass from (0,0) based on previous UPPER & LEFT cell
        int[][] directions={ {-1,0}, {0,-1} };

        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                neighborValue=10000000;

                // Check only previous LEFT & UPPER adjacent cells
                for(int[] dir:directions){
                    int nr=i+dir[0];
                    int nc=j+dir[1];

                    // If adjacent cell is within boundary
                    if(nr>=0 && nr<m && nc>=0 && nc<n){                        
                        neighborValue=Math.min(neighborValue, matrix[nr][nc]);
                    } 
                }

                matrix[i][j]=Math.min(matrix[i][j], neighborValue+1);
            }
        }


        // Backward Pass from (m-1,n-1) based on previous DOWN & RIGHT cell
        directions=new int[][]{ {1,0}, {0,1} };
        for(int i=m-1; i>=0; i--){
            for(int j=n-1; j>=0; j--){
                neighborValue=10000000;

                // Check only previous RIGTH & DOWN adjacent cells
                for(int[] dir:directions){
                    int nr=i+dir[0];
                    int nc=j+dir[1];

                    // If adjacent cell is within boundary
                    if(nr>=0 && nr<m && nc>=0 && nc<n){                        
                        neighborValue=Math.min(neighborValue, matrix[nr][nc]);
                    } 
                }

                matrix[i][j]=Math.min(matrix[i][j], neighborValue+1);
            }
        }


        return matrix;
    }

}
```
['Breadth-First Search', 'Matrix', 'Python', 'Java', 'Python3']