Problem Statement
In the given problem, we are provided with an integer matrix isWater of dimensions m x n, where each element of the matrix signifies whether a cell is water or land. Specifically, a value of 1 indicates a water cell, and 0 indicates a land cell. Our goal is to assign a non-negative height to each cell. Water cells must have a height of zero and land cells should be assigned heights following a specific rule: The absolute height difference between any two adjacent cells must not exceed one. An adjacent cell is one that lies directly north, south, east, or west of another cell.
The objective is to determine an assignment of heights where the maximum height of any land cell is as large as possible, given the constraints. This task is a bit tricky as the solution should not only follow the adjacency rule but also maximize the height difference to achieve the tallest possible configuration without breaking the adjacency rule on cell heights.
Examples
Example 1
Input:
isWater = [[0,1],[0,0]]
Output:
[[1,0],[2,1]]
Explanation:
The image shows the assigned heights of each cell. The blue cell is the water cell, and the green cells are the land cells.
Example 2
Input:
isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output:
[[1,1,0],[0,1,1],[1,2,2]]
Explanation:
A height of 2 is the maximum possible height of any assignment. Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.
Constraints
m == isWater.lengthn == isWater[i].length1 <= m, n <= 1000isWater[i][j]is0or1.- There is at least one water cell.
Approach and Intuition
Given the constraints and rules, let's break down the approach:
Initialization:
- We begin with initializing all water cells with a height of
0since that is explicitly stated in the problem. - Since the goal is to maximize the height of land cells, we can utilize a BFS (Breadth-First Search) approach starting from all water cells.
- We begin with initializing all water cells with a height of
Implementing BFS:
- Enqueue all water cells as starting points in our BFS, as these are the only cells with a predetermined height.
- Intuitively, the height of any land cell will be determined based on its shortest distance to the nearest water cell, given that each move away from a water cell increments the height by one.
Processing Neighbors:
- For each cell being processed in the BFS, check its four possible neighbors (north, south, east, and west).
- If a neighbor is a land cell and hasn't been assigned a height yet, or if a smaller height can be assigned (ensuring each step away from water increments height by one), update its height and enqueue it for further processing.
Height Maximization:
- Since BFS processes levels in waves from the starting points, land cells farther from the initial water cells naturally achieve higher heights as the BFS progresses. This is how the height maximization is implicitly handled.
- Each land cell will essentially receive a height equal to its shortest path (in terms of steps) to the nearest water cell.
Termination:
- The BFS completes when all possible cells are visited and no further updates are needed. This ensures that all cells are set to the optimal heights adhering to the conditions provided.
Edge Cases and Complexity Considerations: * For mazes where land surrounds a small area of water or vice versa, the BFS efficiently handles incrementally assigning heights. * As BFS is linear in the number of cells, the given constraints (up to 1000x1000 matrix) will operate in feasible time.
Through this systematic and iterative approach, the proposed BFS strategy optimally assigns heights while ensuring that each land cell's height is as tall as feasible, given its proximity to water cells.
Solutions
- C++
- Java
- Python
class Solution {
public:
vector<vector<int>> generateHeights(vector<vector<int>>& waterMap) {
const int m = waterMap.size();
const int n = waterMap[0].size();
const int HIGH_VALUE = m * n;
vector<vector<int>> heights(m, vector<int>(n, HIGH_VALUE));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (waterMap[i][j]) {
heights[i][j] = 0;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int lowest_neighbor = HIGH_VALUE;
int upRow = i - 1;
int upCol = j;
if (checkCell(upRow, upCol, m, n)) {
lowest_neighbor = min(lowest_neighbor, heights[upRow][upCol]);
}
int leftRow = i;
int leftCol = j - 1;
if (checkCell(leftRow, leftCol, m, n)) {
lowest_neighbor = min(lowest_neighbor, heights[leftRow][leftCol]);
}
heights[i][j] = min(heights[i][j], lowest_neighbor + 1);
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
int lowest_neighbor = HIGH_VALUE;
int downRow = i + 1;
int downCol = j;
if (checkCell(downRow, downCol, m, n)) {
lowest_neighbor = min(lowest_neighbor, heights[downRow][downCol]);
}
int rightRow = i;
int rightCol = j + 1;
if (checkCell(rightRow, rightCol, m, n)) {
lowest_neighbor = min(lowest_neighbor, heights[rightRow][rightCol]);
}
heights[i][j] = min(heights[i][j], lowest_neighbor + 1);
}
}
return heights;
}
private:
bool checkCell(int row, int col, int maxRow, int maxCol) {
return row >= 0 && col >= 0 && row < maxRow && col < maxCol;
}
};
In the provided C++ solution for generating a height map from a water map, you work with a 2D grid. The objective is to assign heights to each cell starting from zero at water cells and increasing the height for land cells, ensuring that every cell's height is minimal based on proximity to the nearest water cell.
- Start by initializing the height of every cell to a large value.
- Set the heights of water cells (cells containing
1) in thewaterMapto zero. - Process each cell in the grid to compute its height based on the heights of its neighbors. This involves:
- Checking available neighboring cells (up and left) and updating the current cell’s height to be one plus the minimum height of these neighbors, provided the current cell is not already set to zero.
- Repeat the height determination from the opposite direction—down and right neighbors to ensure each cell is assigned the lowest possible value considering all four potential neighbor directions.
The solution leverages the helper function checkCell to verify if a given cell index (row, column) is valid. This prevents out-of-bound errors by ensuring indices are within the grid limits.
By adapting the heights after each full grid scan, and then re-evaluating to potentially lower them further in a second pass, the function aims to output a grid (heights) where each land cell has the smallest possible height that maintains integer height differences between any accessible neighboring cells, adhering to constraints driven by proximity to the nearest water cells.
public class Solution {
public int[][] calculatePeaks(int[][] waterMap) {
int rowNum = waterMap.length;
int colNum = waterMap[0].length;
final int MAX_DIST = rowNum * colNum; // Used as initial distance
int[][] peakHeights = new int[rowNum][colNum];
for (int[] heightRow : peakHeights) {
Arrays.fill(heightRow, MAX_DIST);
}
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (waterMap[i][j] == 1) {
peakHeights[i][j] = 0;
}
}
}
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
int minDist = MAX_DIST;
if (cellExists(i - 1, j, rowNum, colNum)) {
minDist = Math.min(minDist, peakHeights[i - 1][j]);
}
if (cellExists(i, j - 1, rowNum, colNum)) {
minDist = Math.min(minDist, peakHeights[i][j - 1]);
}
peakHeights[i][j] = Math.min(peakHeights[i][j], minDist + 1);
}
}
for (int i = rowNum - 1; i >= 0; i--) {
for (int j = colNum - 1; j >= 0; j--) {
int minDist = MAX_DIST;
if (cellExists(i + 1, j, rowNum, colNum)) {
minDist = Math.min(minDist, peakHeights[i + 1][j]);
}
if (cellExists(i, j + 1, rowNum, colNum)) {
minDist = Math.min(minDist, peakHeights[i][j + 1]);
}
peakHeights[i][j] = Math.min(peakHeights[i][j], minDist + 1);
}
}
return peakHeights;
}
private boolean cellExists(int i, int j, int maxRow, int maxCol) {
return i >= 0 && j >= 0 && i < maxRow && j < maxCol;
}
}
This Java solution focuses on calculating peak heights from a given water map using a multi-pass flood fill algorithm.
Initial set up involves creating an array, peakHeights, initialized to a high value representing maximum distances. Cells in waterMap containing water (represented by 1) are set to 0 in peakHeights, indicating the shortest distance.
The program executes two main loops:
- The first pass progresses from the top-left towards the bottom-right. For each cell, it computes the minimum distance from either the top or the left neighboring cell using the previously calculated values.
- The second pass moves from the bottom-right towards the top-left, this time comparing each cell's distance with its bottom and right neighbors. This ensures each cell's height is the minimum value reached from any adjacent filled cell.
The method cellExists() checks boundary conditions to prevent access outside the array bounds.
By iterating in two directions, the program effectively spreads out the height values from the water sources, allowing it to calculate peak distributions based on proximity to the nearest water source accurately. The method returns the filled peakHeights array representing distances to the nearest water-filled cell.
class Solution:
def calculatePeak(self, water_map: List[List[int]]) -> List[List[int]]:
num_rows = len(water_map)
num_cols = len(water_map[0])
max_distance = num_rows * num_cols
heights = [[max_distance] * num_cols for _ in range(num_rows)]
for i in range(num_rows):
for j in range(num_cols):
if water_map[i][j] == 1:
heights[i][j] = 0
for i in range(num_rows):
for j in range(num_cols):
if i > 0:
heights[i][j] = min(heights[i][j], heights[i-1][j] + 1)
if j > 0:
heights[i][j] = min(heights[i][j], heights[i][j-1] + 1)
for i in range(num_rows-1, -1, -1):
for j in range(num_cols-1, -1, -1):
if i < num_rows - 1:
heights[i][j] = min(heights[i][j], heights[i+1][j] + 1)
if j < num_cols - 1:
heights[i][j] = min(heights[i][j], heights[i][j+1] + 1)
return heights
def is_within_bounds(self, x: int, y: int, height: int, width: int) -> bool:
return 0 <= x < height and 0 <= y < width
The provided Python code defines a class Solution with methods to calculate the height map of the highest peaks relative to water locations given in a 2D grid. The code consists of two main parts:
calculatePeak Method:
- Initializes the
heightsarray with a very high value for each cell, to be minimized later. - Sets the height of water locations (value
1in thewater_map) to0. - Uses a two-pass algorithm to propagate the minimum possible heights from the known water locations:
- The first loop moves left to right and top to bottom, adjusting heights based on the minimum height of the top and left neighbors plus one.
- The second loop moves in the opposite direction (right to left and bottom to top) updating heights based on bottom and right neighbors.
- This method returns the height map as a 2D list after both passes, representing the shortest distance to the nearest water cell.
- Initializes the
is_within_bounds Method:
- Checks whether a given position is within the bounds of the grid. This helper function validates if coordinates
(x, y)are within a grid ofheightandwidth.
- Checks whether a given position is within the bounds of the grid. This helper function validates if coordinates
Review the approach outlined in the calculatePeak method to ensure it meets the requirements of creating a height map around water cells, capturing the shortest path the terrain has to rise from any given land cell to the nearest water cell. The second method, is_within_bounds, is generally a utility to help with boundary checks but is unused in the current solution provided.
No comments yet.