Introduction

In this blog post, we will explore how to solve the LeetCode problem "2812" 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 a 0-indexed 2D matrix grid of size n x n, where (r, c) represents: A cell containing a thief if grid[r][c] = 1 An empty cell if grid[r][c] = 0 You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves. The safeness factor of a path on the grid is defined as the minimum manhattan distance from any cell in the path to any thief in the grid. Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1). An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists. The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val. Example 1: Input: grid = [[1,0,0],[0,0,0],[0,0,1]] Output: 0 Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1). Example 2: Input: grid = [[0,0,1],[0,0,0],[0,0,0]] Output: 2 Explanation: The path depicted in the picture above has a safeness factor of 2 since: - The closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2. It can be shown that there are no other paths with a higher safeness factor. Example 3: Input: grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]] Output: 2 Explanation: The path depicted in the picture above has a safeness factor of 2 since: - The closest cell of the path to the thief at cell (0, 3) is cell (1, 2). The distance between them is | 0 - 1 | + | 3 - 2 | = 2. - The closest cell of the path to the thief at cell (3, 0) is cell (3, 2). The distance between them is | 3 - 3 | + | 0 - 2 | = 2. It can be shown that there are no other paths with a higher safeness factor. Constraints: 1 <= grid.length == n <= 400 grid[i].length == n grid[i][j] is either 0 or 1. There is at least one thief in the grid.

Explanation

Here's a breakdown of the solution approach, followed by the code:

• Calculate Safeness Values: First, compute the safeness value for each cell in the grid. This value represents the minimum Manhattan distance from that cell to the nearest thief. We can achieve this efficiently using Breadth-First Search (BFS) starting from all thief locations.

• Binary Search for Maximum Safeness: Perform a binary search on the possible safeness factor values (from 0 to the maximum possible distance which is basically 2*n). For each candidate safeness factor, check if there exists a path from (0, 0) to (n-1, n-1) where all cells in the path have a safeness value greater than or equal to the candidate.

• Check Path Existence with DFS/BFS: Within the binary search, use Depth-First Search (DFS) or Breadth-First Search (BFS) to determine if a path exists from (0, 0) to (n-1, n-1) using only cells with safeness values greater than or equal to the current candidate.

• Runtime Complexity: O(n² log n), where n is the size of the grid. The BFS for calculating safeness takes O(n²), and the binary search takes O(log n) iterations. In each binary search iteration, the DFS or BFS takes O(n²).

• Storage Complexity: O(n²) to store the safeness values grid and the visited array for DFS/BFS.

Code

    from collections import deque

def maximumSafenessFactor(grid):
    n = len(grid)

    def calculate_safeness():
        safeness = [[float('inf')] * n for _ in range(n)]
        queue = deque()
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    safeness[r][c] = 0
                    queue.append((r, c))

        while queue:
            r, c = queue.popleft()
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and safeness[nr][nc] == float('inf'):
                    safeness[nr][nc] = safeness[r][c] + 1
                    queue.append((nr, nc))
        return safeness

    safeness_grid = calculate_safeness()

    def can_reach_destination(min_safeness):
        visited = [[False] * n for _ in range(n)]
        queue = deque([(0, 0)])
        visited[0][0] = True

        while queue:
            r, c = queue.popleft()
            if r == n - 1 and c == n - 1:
                return True

            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and safeness_grid[nr][nc] >= min_safeness:
                    visited[nr][nc] = True
                    queue.append((nr, nc))
        return False

    low = 0
    high = 2 * n  # Maximum possible Manhattan distance
    ans = 0

    while low <= high:
        mid = (low + high) // 2
        if can_reach_destination(mid):
            ans = mid
            low = mid + 1
        else:
            high = mid - 1

    return ans