1765. Map of Highest Peak 🗺️ || Detailed Explanation
1765. Map of Highest Peak 🗺️View Problem on LeetCode | My leetcode ProfileHey there, curious coder! 👋 Ready to explore the peaks and valleys of this fascinating
# 1765. Map of Highest Peak 🗺️

[View Problem on LeetCode](https://leetcode.com/problems/map-of-highest-peak/) | [My leetcode Profile](https://leetcode.com/anil_kumt/)

Hey there, curious coder! 👋 Ready to explore the peaks and valleys of this fascinating problem? Let's dive into a beautiful journey of grid traversal and height mapping! 🚀

## Problem Statement 📜

You're given a magical map (matrix) where:
- 🌊 Water cells are marked as `1`
- 🌿 Land cells are marked as `0`

Your mission, should you choose to accept it:
1. Assign heights to all cells
2. Water cells must be height 0
3. Adjacent cells can only differ by 1 in height
4. Maximize the highest possible peak!

## Example Walkthroughs 🎯

### Example 1: Small Grid

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

**Process:**
1. Water cell (0,1) must be 0
2. Adjacent cells can be 1
3. Bottom-right can be 1 or 2

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

### Example 2: Larger Grid

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

**Visual Process:**

![image.png](https://assets.leetcode.com/users/images/62ea1749-2831-4199-b69b-94e34626b0cb_1737519020.9466562.png)


## The "Aha!" Moment 💡

Think of water cells as the starting points of waves! 🌊
1. Water cells are at sea level (height 0)
2. Each wave of BFS increases height by 1
3. The further from water, the higher the peak!

## Solution Approaches 🛠️

### 1. C++ Solution (Detailed Implementation) 🔥

```cpp
class Solution { 
public:     
    /*     
    To solve this problem ==>      
    1. First we initialize a 2D array with -1 (since it is given that height cannot be negative,
       through '-1', we will know that it is not filled yet) in all cells, let's call it height.      
    2. Then our task is to fill each cell such that all the rules are followed.      
    3. Since one of the rule is that water cell has height zero, we can simply fill our heights matrix,
       by checking on isWater matrix.      
    4. How do we fill rest of the cell?         
       i.  row-wise traversal?         
       ii. Column-wise traversal?         
       iii.Breadth-first search(BFS)?         
       iv. Depth-first search(DFS)?      
    5. It is very obvious that row and column traversal wouldn't help because, we have to keep checking
       all the adjacent cell (right,left,up,down) for each cell, which would not be possible.      
    6. Thinking of DFS? Well that would cause the same problem, since we will be exploring the depth
       first that adjacent.      
    7. So, what did we understand? We need to traverse such that we are able to track the closest
       vertices first and till now you must have guessed it is BFS.      
    8. But what is going to be the source node or root node for the BFS traversal.      
    9. Well which nodes do we know from heights matrix? which are water cells right?      
    10.But there are multiple water source? Yes, So we use "Multiple Source BFS" here.     
    */     
    typedef pair<int,int> P;     
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {         
        // Initial declarations of variables and data structures.         
        int m = isWater.size();         
        int n = isWater[0].size();         
        vector<vector<int>> heights(m,vector<int>(n,-1));         
        queue<P> q;         
        vector<vector<int>> directions = {{0,1},{0,-1},{-1,0},{1,0}};         
        
        // Filling water height with zero, at the same time inserting them in queue
        // (Question says there can be multiple solutions, that's because you can insert
        // source nodes in queue in multiple ways, here we are doing row-wise)         
        for(int i=0;i<m;i++){             
            for(int j=0;j<n;j++){                 
                if(isWater[i][j]==1){                     
                    heights[i][j]=0;                     
                    q.push({i,j});                 
                }             
            }         
        }          
        
        while(!q.empty()){             
            pair<int,int> top = q.front();             
            q.pop();              
            int x = top.first;             
            int y = top.second;              
            
            for(int i=0;i<4;i++){                 
                int new_x = x + directions[i][0];                 
                int new_y = y + directions[i][1];                  
                
                if(new_x>=0 && new_x<m && new_y>=0 && new_y<n && heights[new_x][new_y]==-1){                     
                    heights[new_x][new_y] = heights[x][y] + 1;                     
                    q.push({new_x,new_y});                 
                }              
            }         
        }         
        return heights;     
    } 
};
```

### 2. Python Solution 🐍

```python
from collections import deque

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        heights = [[-1] * n for _ in range(m)]
        queue = deque()
        
        # Initialize water cells 🌊
        for i in range(m):
            for j in range(n):
                if isWater[i][j]:
                    heights[i][j] = 0
                    queue.append((i, j))
        
        # BFS traversal 🏃
        while queue:
            x, y = queue.popleft()
            for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and heights[nx][ny] == -1:
                    heights[nx][ny] = heights[x][y] + 1
                    queue.append((nx, ny))
        
        return heights
```

### 3. Java Solution ☕

```java
class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        int[][] heights = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        
        // Initialize heights array with -1 and find water cells
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    heights[i][j] = 0;
                    queue.offer(new int[]{i, j});
                } else {
                    heights[i][j] = -1;
                }
            }
        }
        
        // Directions for adjacent cells
        int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        // BFS to fill heights
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];
            
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && heights[nx][ny] == -1) {
                    heights[nx][ny] = heights[x][y] + 1;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        
        return heights;
    }
}
```

### 4. JavaScript Solution 🟨

```javascript
/**
 * @param {number[][]} isWater
 * @return {number[][]}
 */
var highestPeak = function(isWater) {
    const m = isWater.length, n = isWater[0].length;
    const heights = Array(m).fill().map(() => Array(n).fill(-1));
    const queue = [];
    
    // Find water cells and initialize them
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (isWater[i][j] === 1) {
                heights[i][j] = 0;
                queue.push([i, j]);
            }
        }
    }
    
    // Directions for adjacent cells
    const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
    
    // BFS implementation
    while (queue.length > 0) {
        const [x, y] = queue.shift();
        
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && heights[nx][ny] === -1) {
                heights[nx][ny] = heights[x][y] + 1;
                queue.push([nx, ny]);
            }
        }
    }
    
    return heights;
};
```

[Rest of the content remains the same...]

## Time & Space Complexity ⚡

### Time Complexity
- 🕒 O(m × n) - We visit each cell exactly once

### Space Complexity
- 🗃️ O(m × n) - For the heights matrix and queue

## Common Pitfalls to Avoid ⚠️

1. Don't forget to initialize water cells to 0
2. Remember to check boundary conditions
3. Ensure all cells are reachable
4. Don't modify the input matrix

## Pro Tips 🌟

1. Use BFS when dealing with shortest paths or minimum differences
2. Multi-source BFS is perfect for problems with multiple starting points
3. Queue-based approach ensures minimum height difference constraint

## Follow-up Questions 🤔

1. How would you handle if diagonal moves were allowed?
2. What if some land cells had minimum height requirements?
3. Can you solve it with O(1) extra space?

## Final Thoughts 💭

This problem beautifully demonstrates:
- The power of BFS in grid problems
- How to handle multiple constraints elegantly
- The importance of choosing the right data structures

Remember: "The best code is not always the cleverest, but the most maintainable!" 🎯

Happy Coding! 🎉

---
If this helped you crack the problem, don't forget to give it a star! ⭐️

*P.S. Want to practice more grid problems? Check out [these similar problems](https://leetcode.com/tag/breadth-first-search/)!*
['Array', 'Breadth-First Search', 'C++', 'Java', 'Python3', 'JavaScript']