BFS solution || Proper Explanation || Complexities Explained
IntuitionThe problem involves assigning heights to cells in a grid such that:
Water cells are assigned a height of 0.
Heights of adjacent cells differ by at mos
# Intuition
The problem involves assigning heights to cells in a grid such that:
1. Water cells are assigned a height of 0.
2. Heights of adjacent cells differ by at most 1.
3. Heights increase as we move away from water cells.

This naturally leads to a layered propagation of heights starting from water cells. Using BFS ensures that we visit cells layer by layer, where each layer represents cells at the same distance from the nearest water cell.

# Approach
1. **Initialization:**
   - Create a grid `ans` initialized with -1 (indicating unvisited cells).
   - Use the `isWater` grid to identify water cells, set their heights in `ans` to 0, and enqueue their positions.

2. **BFS Propagation:**
   - BFS processes cells in a "wavefront" manner, starting from all water cells.
   - For each cell in the queue, check its four neighbors (up, down, left, right).
   - If a neighbor is unvisited (i.e., height is -1), assign it a height one greater than the current cell and add it to the queue.

3. **Termination:**
   - BFS continues until all reachable cells have been visited.
   - The `ans` grid now contains the desired heights for all cells.

# Why and How This Works
1. **Why BFS?**
   - BFS processes cells level by level, starting from the source cells (water cells with height 0).
   - This ensures that the first time a cell is visited, it is assigned the minimum possible height while maintaining the height difference constraint.

2. **How Propagation Works:**
   - When a cell is dequeued, it has the minimum height possible for its position.
   - Its neighbors are assigned heights incrementally (current height + 1), ensuring the height difference between adjacent cells is at most 1.

3. **Layered Growth:**
   - Imagine water spreading outward in concentric circles. BFS replicates this process by growing heights layer by layer, starting from the water cells.

4. **Ensuring Maximum Height:**
   - Cells farthest from water cells will naturally have the highest height, as BFS assigns heights incrementally based on distance from water.

# Complexity

- **Time Complexity:** $$O(m \times n)$$  
  The time complexity is dominated by the BFS traversal:
  1. Each cell in the grid is processed exactly **once** during the BFS. This means the `while` loop runs for at most $$m \times n$$ iterations, where $$m$$ is the number of rows and $$n$$ is the number of columns in the grid.
  2. For each cell, we check its **4 possible neighbors** (north, south, east, and west). However, this neighbor-checking is constant per cell and does not scale beyond the $$m \times n$$ total cells.
  3. Thus, the total work done is proportional to the number of cells, making the time complexity $$O(m \times n)$$.

- **Space Complexity:** $$O(m \times n)$$  
  1. The `ans` matrix of size $$m \times n$$ stores the height of each cell.  
  2. The BFS queue can also hold up to $$O(m \times n)$$ elements in the worst case (when all cells are processed in one BFS traversal).
  3. Together, the space used for the matrix and the queue leads to a space complexity of $$O(m \times n)$$.

### Additional Insights:
- **Why the `while` loop isn't a separate factor in the complexity:**  
  The `while` loop iterates for as long as there are elements in the queue. Each cell is added to the queue exactly **once** and removed exactly **once**, meaning the total number of iterations of the `while` loop is $$m \times n$$, matching the total number of cells. This is already accounted for in the $$O(m \times n)$$ complexity.

- **Why the BFS neighbor-checking doesn't increase complexity:**  
  Even though each cell checks up to 4 neighbors, this doesn't create additional complexity because each neighbor is only checked **once** when it is dequeued from the queue. The total number of neighbor-checks is therefore bounded by the number of edges in the grid graph, which is proportional to the number of cells, i.e., $$O(m \times n)$$.

- **Worst-case scenario:**  
  If the grid consists entirely of land (i.e., no water cells), all $$m \times n$$ cells will be processed in the BFS, and the queue will grow to its maximum size. This is the worst-case scenario, but it still adheres to the $$O(m \times n)$$ time and space bounds.


# Code
``` cpp []
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int n = isWater.size();
        int m = isWater[0].size();
        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) {
                    q.push({i, j});
                    ans[i][j] = 0;
                }
            }
        }

        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        while (!q.empty()) {
            int row = q.front().first;
            int col = q.front().second;
            q.pop();

            for (auto dir : directions) {
                int newRow = dir[0] + row;
                int newCol = dir[1] + col;

                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m &&
                    ans[newRow][newCol] == -1) {
                    ans[newRow][newCol] = ans[row][col] + 1;

                    q.push({newRow, newCol});
                }
            }
        }

        return ans;
    }
};
```
```python []
class Solution:
    def highestPeak(self, isWater: list[list[int]]) -> list[list[int]]:
        n = len(isWater)
        m = len(isWater[0])
        ans = [[-1] * m for _ in range(n)]
        q = deque()

        for i in range(n):
            for j in range(m):
                if isWater[i][j] == 1:
                    q.append((i, j))
                    ans[i][j] = 0

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

        while q:
            row, col = q.popleft()

            for dr, dc in directions:
                newRow, newCol = row + dr, col + dc

                if 0 <= newRow < n and 0 <= newCol < m and ans[newRow][newCol] == -1:
                    ans[newRow][newCol] = ans[row][col] + 1
                    q.append((newRow, newCol))

        return ans

```
['Array', 'Breadth-First Search', 'Matrix', 'C++', 'Python3']