🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
IntuitionThe problem requires us to determine the heights of land cells in a grid based on the proximity to water cells. Water cells have a height of 0, and lan
![image.png](https://assets.leetcode.com/users/images/8d185c62-e1ca-44f8-8e64-7d6252eca77a_1737562224.8011582.png)

---
![1000069650.png](https://assets.leetcode.com/users/images/ba1f5296-620a-4423-b83c-aee6e26ed88e_1737565469.0942984.png)

---


## Intuition
The problem requires us to determine the heights of land cells in a grid based on the proximity to water cells. Water cells have a height of 0, and land cells should have heights that represent their distance from the nearest water cell. My initial thought is to use a breadth-first search (BFS) approach starting from all water cells simultaneously, propagating outward to calculate the height of each land cell.

## Approach
1. **Initialization**:
   - Create a queue to facilitate BFS and a result matrix (`res`) initialized with -1, indicating unvisited land cells.
   - Iterate through the input grid (`isWater`) to identify water cells (cells with value 1). Set their corresponding positions in the result matrix to 0 (indicating height) and add them to the queue.

2. **BFS Traversal**:
   - While there are cells in the queue, remove the front cell and explore its four neighboring cells (up, right, down, left).
   - For each neighbor:
     - Check if it is within bounds and has not been visited (i.e., its value in `res` is still -1).
     - If valid, set its height in `res` to be one more than the current cell's height.
     - Add the neighbor to the queue for further exploration.

3. **Return Result**:
   - After processing all reachable cells, return the result matrix containing heights for all land cells.

### Code Examples

```cpp []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        vector<vector<int>> dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        queue<pair<int, int>> q;
        int rows = isWater.size();
        int cols = isWater[0].size();
        
        // Result matrix initialized with -1
        vector<vector<int>> res(rows, vector<int>(cols, -1));

        // Initialize water cells with height 0 and add them to the queue
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (isWater[i][j] == 1) {
                    res[i][j] = 0;
                    q.push({i, j});
                }
            }
        }

        // BFS to assign heights
        while (!q.empty()) {
            auto cell = q.front();
            q.pop();
            int r = cell.first;
            int c = cell.second;

            // Explore all 4 directions
            for (const auto& d : dir) {
                int newR = r + d[0];
                int newC = c + d[1];

                // Check bounds and if the cell has not been visited
                if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && res[newR][newC] == -1) {
                    res[newR][newC] = res[r][c] + 1; // Assign height
                    q.push({newR, newC}); // Add new cell to the queue
                }
            }
        }

        return res;
    }
};
```

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

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int rows = isWater.length;
        int cols = isWater[0].length;
        
        // Directions for moving up, right, down, and left
        int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        
        // Queue for BFS
        Queue<int[]> q = new LinkedList<>();
        int[][] res = new int[rows][cols];

        // Initialize water cells with height 0 and add them to the queue
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (isWater[i][j] == 1) {
                    res[i][j] = 0;
                    q.offer(new int[]{i, j});
                } else {
                    res[i][j] = -1; // Mark land cells as unvisited
                }
            }
        }

        // BFS to assign heights
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int r = cell[0];
            int c = cell[1];

            // Explore all 4 directions
            for (int[] d : dir) {
                int newR = r + d[0];
                int newC = c + d[1];

                // Check bounds and if the cell has not been visited
                if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && res[newR][newC] == -1) {
                    res[newR][newC] = res[r][c] + 1; // Assign height
                    q.offer(new int[]{newR, newC}); // Add new cell to the queue
                }
            }
        }

        return res;
    }
}
```

```javascript []
class Solution {
    highestPeak(isWater) {
        const rows = isWater.length;
        const cols = isWater[0].length;

        // Directions for moving up, right, down, and left
        const dir = [[-1, 0], [0, 1], [1, 0], [0, -1]];

        // Queue for BFS
        const q = [];
        const res = Array.from({ length: rows }, () => Array(cols).fill(-1));

        // Initialize water cells with height 0 and add them to the queue
        for (let i = 0; i < rows; i++) {
            for (let j = 0; j < cols; j++) {
                if (isWater[i][j] === 1) {
                    res[i][j] = 0;
                    q.push([i, j]);
                }
            }
        }

        // BFS to assign heights
        while (q.length > 0) {
            const [r, c] = q.shift();

            // Explore all 4 directions
            for (const [dr, dc] of dir) {
                const newR = r + dr;
                const newC = c + dc;

                // Check bounds and if the cell has not been visited
                if (newR >= 0 && newR < rows && newC >= 0 && newC < cols && res[newR][newC] === -1) {
                    res[newR][newC] = res[r][c] + 1; // Assign height
                    q.push([newR, newC]); // Add new cell to the queue
                }
            }
        }

        return res;
    }
}
```

```python []
from collections import deque

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        rows = len(isWater)
        cols = len(isWater[0])
        
        # Directions for moving up, right, down, and left
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        
        # Queue for BFS and result matrix initialized with -1
        q = deque()
        res = [[-1] * cols for _ in range(rows)]

        # Initialize water cells with height 0 and add them to the queue
        for i in range(rows):
            for j in range(cols):
                if isWater[i][j] == 1:
                    res[i][j] = 0
                    q.append((i, j))

        # BFS to assign heights
        while q:
            r, c = q.popleft()

            # Explore all four directions
            for dr, dc in directions:
                new_r, new_c = r + dr, c + dc

                # Check bounds and if the cell has not been visited yet
                if 0 <= new_r < rows and 0 <= new_c < cols and res[new_r][new_c] == -1:
                    res[new_r][new_c] = res[r][c] + 1 # Assign height based on current cell's height
                    q.append((new_r, new_c)) # Add new cell to the queue

        return res
```

```dart []
import 'dart:collection';

class Solution {
  List<List<int>> highestPeak(List<List<int>> isWater) {
    // Directions for moving up, right, down, and left
    List<List<int>> dir = [
      [-1, 0],
      [0, 1],
      [1, 0],
      [0, -1],
    ];

    // Queue for BFS
    final q = Queue<List<int>>();
    int rows = isWater.length;
    int cols = isWater[0].length;

    // Result matrix initialized with -1
    List<List<int>> res =
      List.generate(rows, (i) => List.generate(cols, (x) => -1));

    // Initialize water cells with height 0 and add them to the queue
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
          if (isWater[i][j] == 1) {
              res[i][j] = 0;
              q.add([i,j]);
          }
      }
    }

    // BFS to assign heights 
    while(q.isNotEmpty){
      List<int> cell= q.removeFirst();
      int r=cell[0];
      int c=cell[1];

      // Explore all four directions 
      for(int i=0;i<dir.length;i++){
          int newR=r+dir[i][0];
          int newC=c+dir[i][1];

          // Check bounds and if the cell has not been visited 
          if(newR>=0 && newR<rows && 
             newC>=0 && newC<cols &&
             res[newR][newC]==-1){
              res[newR][newC]=res[r][c]+1; 
              q.add([newR,newC]); 
          }
      }
    }

    return res;
  }
}
```

## Complexity

- **Time complexity**: $$O(n \cdot m)$$ where $$n$$ is the number of rows and $$m$$ is the number of columns in `isWater`. This accounts for initializing prefix sums and performing BFS traversal.

- **Space complexity**: $$O(n \cdot m)$$ due to storing results in a separate matrix (`res`) as well as maintaining a queue that could hold at most $$n \cdot m$$ elements in case every cell needs processing.

---

![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style='width:250px'}
['Array', 'Breadth-First Search', 'C', 'Matrix', 'C++', 'Java', 'Python3', 'JavaScript', 'Dart']