Introduction

In this blog post, we will explore how to solve the LeetCode problem "1765" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given an integer matrix isWater of size m x n that represents a map of land and water cells. If isWater[i][j] == 0, cell (i, j) is a land cell. If isWater[i][j] == 1, cell (i, j) is a water cell. You must assign each cell a height in a way that follows these rules: The height of each cell must be non-negative. If the cell is a water cell, its height must be 0. Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching). Find an assignment of heights such that the maximum height in the matrix is maximized. Return an integer matrix height of size m x n where height[i][j] is cell (i, j)'s height. If there are multiple solutions, return any of them. 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.length n == isWater[i].length 1 <= m, n <= 1000 isWater[i][j] is 0 or 1. There is at least one water cell. Note: This question is the same as 542: https://leetcode.com/problems/01-matrix/

Explanation

• Initialization: Start by assigning a height of 0 to all water cells and a large value (e.g., infinity or a large number greater than any possible height) to all land cells.
  • Breadth-First Search (BFS): Perform a BFS starting from the water cells. For each land cell encountered during the BFS, update its height to be one greater than the height of the adjacent cell from which it was reached.
  • Iterative Relaxation: Continue the BFS until all land cells have their minimum possible height assigned based on their proximity to water cells.

• Runtime Complexity: O(m*n), where m and n are the dimensions of the matrix. Storage Complexity: O(m*n).

Code

    from collections import deque

def highestPeak(isWater):
    m, n = len(isWater), len(isWater[0])
    height = [[float('inf')] * n for _ in range(m)]
    queue = deque()

    for i in range(m):
        for j in range(n):
            if isWater[i][j] == 1:
                height[i][j] = 0
                queue.append((i, j))

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc

            if 0 <= new_row < m and 0 <= new_col < n and height[new_row][new_col] > height[row][col] + 1:
                height[new_row][new_col] = height[row][col] + 1
                queue.append((new_row, new_col))

    return height