BFS | Hashing | Why BFS Explained | 100% BEATS
IntuitionThe problem is about assigning heights to cells such that:
Water cells have height 0.
Adjacent cells have at most a height difference of 1.
Maximize th
## Intuition

The problem is about assigning heights to cells such that:
- Water cells have height `0`.
- Adjacent cells have at most a height difference of `1`.
- Maximize the overall height in the grid.
---


## Why BFS?

- **Layer-wise Expansion**: BFS explores each level before moving to the next, matching the need to gradually increase heights from water cells.
- **Optimal Height Assignment**: Starting from water cells, BFS ensures each cell gets the smallest height possible, efficiently meeting the constraints.

---

## BFS

- **Layer-by-Layer**: BFS explores each level before moving outward.
- **Start from Water**: Begins with water cells at height `0`.
- **Minimal Heights**: Ensures each cell gets the smallest height relative to water.
- **Height Difference**: Maintains a height difference of `1` between adjacent cells.

---

## Implementation

```cpp
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> ans(m, vector<int>(n, -1));
        queue<int> q;
        int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j] == 1)
                    ans[i][j] = 0, q.push(i * n + j);

        while (!q.empty()) {
            int x = q.front() / n, y = q.front() % n; q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && ans[nx][ny] == -1)
                    ans[nx][ny] = ans[x][y] + 1, q.push(nx * n + ny);
            }
        }
        return ans;
    }
};
```

---

Let's go through the two examples using the provided images and explain them step by step.

### Example 1:

**Input:**  
`isWater = [[0,1], [0,0]]`

**Output:**  
`[[1,0], [2,1]]`

**Explanation:**

- The grid contains a water cell at `(0,1)` and land cells elsewhere.
- We start with the water cell (`height = 0`), and using **BFS**, we expand to the neighboring cells, increasing the height by 1 for each layer.

#### Steps:
1. Water cell `(0,1)` is assigned height `0`.
2. The neighboring land cells `(0,0)` and `(1,1)` are assigned height `1`.
3. The next neighboring cell `(1,0)` is assigned height `2`.

**Visual:**
![Example 1](https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-82045-am.png)

---

### Example 2:

**Input:**  
`isWater = [[0,0,1], [1,0,0], [0,0,0]]`

**Output:**  
`[[1,1,0], [0,1,1], [1,2,2]]`

**Explanation:**

- There are water cells at `(0,2)` and `(1,0)`.
- Start with these water cells (`height = 0`) and expand outward, incrementing the height by 1 for each layer.

#### Steps:
1. Water cells `(0,2)` and `(1,0)` are assigned height `0`.
2. Neighboring cells `(0,1)`, `(1,1)`, `(2,0)`, and `(1,2)` are assigned height `1`.
3. The next set of neighbors, `(0,0)`, `(2,1)`, and `(2,2)`, are assigned height `2`.

**Visual:**
![Example 2](https://assets.leetcode.com/uploads/2021/01/10/screenshot-2021-01-11-at-82050-am.png)

---

In both examples, **BFS** ensures the smooth propagation of heights from water cells, satisfying the condition of height difference between adjacent cells being at most `1`. This results in the gradual increase in height as we move away from water cells.



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