Most Optimal Solution ✅Beats 100% | C++| Java | Python | JavaScript
⬆️Upvote if it helps ⬆️Connect with me on Linkedin [Bijoy Sing]Intuition 💡Our goal is to build a height map starting from water (height 0) and spreading outward
# ⬆️Upvote if it helps ⬆️

---

## Connect with me on Linkedin [Bijoy Sing]

---

```cpp []
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> height(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        
        // Initialize water cells
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(isWater[i][j]) {
                    height[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        
        // BFS directions
        int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        // BFS from water to land
        while(!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for(auto [dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && height[nx][ny] == -1) {
                    height[nx][ny] = height[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        return height;
    }
};
```
```python []
class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        height = [[-1] * n for _ in range(m)]
        q = deque()
        
        # Initialize water cells
        for i in range(m):
            for j in range(n):
                if isWater[i][j]:
                    height[i][j] = 0
                    q.append((i, j))
        
        # BFS directions
        dirs = [(1,0), (-1,0), (0,1), (0,-1)]
        
        # BFS from water to land
        while q:
            x, y = q.popleft()
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and height[nx][ny] == -1:
                    height[nx][ny] = height[x][y] + 1
                    q.append((nx, ny))
        
        return height
```
```java []
class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length, n = isWater[0].length;
        int[][] height = new int[m][n];
        Queue<int[]> q = new LinkedList<>();
        
        // Initialize water cells
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                height[i][j] = -1;
                if(isWater[i][j] == 1) {
                    height[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }
        
        // BFS directions
        int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        // BFS from water to land
        while(!q.isEmpty()) {
            int[] curr = q.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 && height[nx][ny] == -1) {
                    height[nx][ny] = height[x][y] + 1;
                    q.offer(new int[]{nx, ny});
                }
            }
        }
        return height;
    }
}
```
```javascript []
/**
 * @param {number[][]} isWater - Matrix where 1 represents water cells and 0 represents land cells
 * @return {number[][]} - Matrix of assigned heights where water cells are 0 and adjacent cells differ by at most 1
 */
var highestPeak = function(isWater) {
    const m = isWater.length;
    const n = isWater[0].length;
    const q = [];
    
     const height = isWater.map((row, i) => 
        row.map((cell, j) => {
            if (cell === 1) {
                q.push([i, j, 0]); 
                return 0;
            }
            return Infinity;
        })
    );
    
     let idx = 0;
    while (idx < q.length) {
        const [x, y, h] = q[idx++];
        
        // Check all 4 directions
        if (x > 0 && height[x-1][y] === Infinity) {
            height[x-1][y] = h + 1;
            q.push([x-1, y, h + 1]);
        }
        if (x < m-1 && height[x+1][y] === Infinity) {
            height[x+1][y] = h + 1;
            q.push([x+1, y, h + 1]);
        }
        if (y > 0 && height[x][y-1] === Infinity) {
            height[x][y-1] = h + 1;
            q.push([x, y-1, h + 1]);
        }
        if (y < n-1 && height[x][y+1] === Infinity) {
            height[x][y+1] = h + 1;
            q.push([x, y+1, h + 1]);
        }
    }
    
    return height;
};
```

# Intuition 💡
Our goal is to build a height map starting from water (height 0) and spreading outward. The key insight is that each land cell's height should be determined by its distance from the nearest water cell, while maintaining a maximum difference of 1 between adjacent cells. This naturally points to a BFS approach! 🌊 → 🏔️

# Approach 🎯
1. Start by marking water cells as height 0 and adding them to our BFS queue
2. For each cell in the queue, explore its 4 neighboring cells
3. If a neighbor hasn't been visited, set its height to current cell's height + 1
4. Continue this wave-like expansion until all cells have been assigned heights
   
Think of it like ripples spreading out from multiple water sources! 🌊

![image.png](https://assets.leetcode.com/users/images/9b4e91da-57d0-40f3-b390-e9a300130372_1737531461.214961.png)


# Complexity
- Time complexity: $$O(m \times n)$$ ⏱️ 
  - We visit each cell exactly once during BFS
- Space complexity: $$O(m \times n)$$ 💾
  - Required for the height matrix and queue

### *If you have any questions or need further clarification, feel free to drop a comment! 😊*
['Array', 'Breadth-First Search', 'Matrix', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']