Map of Highest Peak

Leetcode Problem:

• Map of Highest Peak

Summary

• Find an assignment of heights for a given map of land and water cells such that the maximum height in the matrix is maximized.

Approach

• Breadth-First Search (BFS) algorithm is used to traverse the water cells and assign heights to them
• The BFS algorithm starts from the water cells and explores all adjacent cells level by level, ensuring that the height difference between adjacent cells is at most 1.

Complexity

• O(MN)

Explanation

• The BFS algorithm works by maintaining a queue of nodes to visit, where each node represents a water cell
• For each water cell, we explore all its adjacent cells (up, down, left, right) and assign the next available height
• We continue this process until all water cells have been visited.

Solution Code:

struct _node{
    int r;
    int c;
};
class Solution {
public:
    queue<_node> que;
    vector> ans;
    vector> highestPeak(vector>& isWater) {
        int M = isWater.size();
        int N = isWater[0].size();
        for(int i = 0 ; i < M; i++){
            ans.push_back(vector());
            for(int j = 0 ; j < N; j++){
                ans[i].push_back(-1);
                if(isWater[i][j]){
                    que.push({i, j});
                    ans[i][j] = 0;
                }
            }
        }
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        while(!que.empty()){
            _node nod = que.front();
            que.pop();
            for(int i = 0; i < 4; i++){
                int nr = nod.r + dy[i];
                int nc = nod.c + dx[i];
                if(nr < 0 || nr >= M || nc < 0 || nc >= N || ans[nr][nc] != -1){
                    continue;
                }
                ans[nr][nc] = ans[nod.r][nod.c] + 1;
                que.push({nr, nc});
            }
        }
        return ans;
    }
};