Peak Heights 🦖

Description

You are given a two-dimensional integer matrix containing 0s and 1s where 0 represents water and 1 represents land. Return a new matrix of the same dimensions where we increase the height of every land cell as much as possible given that:

• The height of any water cell stays 0
• Any cell can differ by at most 1 unit of height between neighboring cells (up, down, left, right)

You can assume there is at least one water cell.

Constraints:

• n, m ≤ 250 where n and m are the number of rows and columns in matrix

Example 1

Input

matrix = [
    [0, 1, 0],
    [1, 1, 1],
    [1, 1, 1]
]

Output

[
    [0, 1, 0],
    [1, 2, 1],
    [2, 3, 2]
]

---

Intuition

Do multi source BFS from all the water positions i.e 0's by inserting all such cells into a queue

Implementation

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

vector<vector<int>> solve(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    queue<pair<int, int>> q;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] == 0) q.push({i, j});
        }
    }
    int val = 0;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto point = q.front();
            q.pop();
            if (visited[point.first][point.second]) continue;
            visited[point.first][point.second] = true;
            matrix[point.first][point.second] = val;
            for (int j = 0; j < 4; j++) {
                int x = point.first + dx[j], y = point.second + dy[j];
                if (x >= 0 && x < rows && y >= 0 && y < cols && !visited[x][y]) q.push({x, y});
            }
        }
        val++;
    }
    return matrix;
}

Time Complexity

• Time: O(n)
• Space: O(n)