Introduction

In this blog post, we will explore how to solve the LeetCode problem "1293" 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 m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step. Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1. Example 1: Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1 Output: 6 Explanation: The shortest path without eliminating any obstacle is 10. The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2). Example 2: Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output: -1 Explanation: We need to eliminate at least two obstacles to find such a walk. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 40 1 <= k <= m * n grid[i][j] is either 0 or 1. grid[0][0] == grid[m - 1][n - 1] == 0

Explanation

• BFS with State Representation: The problem is solved using Breadth-First Search (BFS). Each state in the BFS represents a cell (row, col) in the grid along with the number of obstacles 'k' remaining that can be eliminated.
  • Visited Set Optimization: A 3D visited array visited[row][col][k] is used to track visited states (row, col, remaining_k). This prevents cycles and redundant exploration of states with the same remaining obstacle elimination capacity.
  • Early Exit: If the maximum possible obstacles that can be eliminated (k) is greater or equal to the total steps needed for the path without obstacles, then we can reach the end node by directly going to the destination and skipping the BFS search.

• Runtime Complexity: O(m n k), where m is the number of rows, n is the number of columns, and k is the maximum obstacles that can be eliminated.
• Storage Complexity: O(m n k)

Code

    from collections import deque

def shortest_path(grid: list[list[int]], k: int) -> int:
    """
    Finds the shortest path from the top-left corner to the bottom-right corner of a grid,
    given that you can eliminate at most k obstacles.

    Args:
        grid: A 2D integer matrix representing the grid, where 0 is empty and 1 is an obstacle.
        k: The maximum number of obstacles that can be eliminated.

    Returns:
        The minimum number of steps to walk from the upper-left corner to the lower-right corner,
        or -1 if no such walk exists.
    """

    m, n = len(grid), len(grid[0])
    if k >= m + n - 2:
      return m + n - 2

    q = deque([(0, 0, k, 0)])  # (row, col, remaining_k, steps)
    visited = [[[False] * (k + 1) for _ in range(n)] for _ in range(m)]
    visited[0][0][k] = True

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

    while q:
        row, col, remaining_k, steps = q.popleft()

        if row == m - 1 and col == n - 1:
            return steps

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

            if 0 <= new_row < m and 0 <= new_col < n:
                if grid[new_row][new_col] == 0 and not visited[new_row][new_col][remaining_k]:
                    q.append((new_row, new_col, remaining_k, steps + 1))
                    visited[new_row][new_col][remaining_k] = True
                elif grid[new_row][new_col] == 1 and remaining_k > 0 and not visited[new_row][new_col][remaining_k - 1]:
                    q.append((new_row, new_col, remaining_k - 1, steps + 1))
                    visited[new_row][new_col][remaining_k - 1] = True

    return -1