Map Of Highest Peak · Interview Problem

Leetcode

map-of-highest-peak

Medium

Graphs

Breadth-First Search

Map Of Highest Peak

Given a matrix that marks water and land cells, assign height values to all land cells such that the height difference between any adjacent cells is at most 1, and water cells have height 0. Return the matrix representing the height map with the highest peak heights.

Acceptance 100%

Start Practice Editorial

Problem Statement

Core description from the backend problem record.

Description

You are given an m x n integer matrix isWater that represents a map of land and water cells.

If isWater[i][j] == 1, cell (i, j) is a water cell. If isWater[i][j] == 0, cell (i, j) is a land cell.

The height of each cell is determined by the following rules:

The height of each water cell is 0.
The height of any land cell must be the minimum distance to any water cell.
Heights must be assigned such that for any two adjacent cells (horizontally or vertically adjacent), the absolute difference in their heights is at most 1.

Return an m x n integer matrix heightMap where heightMap[i][j] is the height of the cell (i, j).

Note: The height of the highest peak should be maximized.

Input Format

A 2D integer matrix isWater of size m x n where:

isWater[i][j] == 1 indicates a water cell.
isWater[i][j] == 0 indicates a land cell.

Output Format

Return a 2D integer matrix heightMap of size m x n where heightMap[i][j] represents the height of the cell (i, j).

Constraints

m == isWater.length n == isWater[i].length 1 <= m, n <= 1000 isWater[i][j] is either 0 or 1 There is at least one water cell in the grid.

Examples

Sample cases returned by the problem API.

Example 1

Input

[[0,1],[0,0]]

Output

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

Explanation

Starting from the water cell (0,1) which has height 0, adjacent land cells (0,0) has height 1, (1,1) has height 1, and (1,0) has height 2.

Loading Preptin

Description

Input Format

Output Format

Constraints