Introduction

In this blog post, we will explore how to solve the LeetCode problem "994" 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 grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1. Example 1: Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4 Example 2: Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally. Example 3: Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 10 grid[i][j] is 0, 1, or 2.

Explanation

Here's the breakdown of the solution:

• Breadth-First Search (BFS): Treat the rotten oranges as starting points for a BFS. Each level of the BFS represents a minute passing, and we spread the rottenness to adjacent fresh oranges.
• Track Fresh Oranges: Keep track of the number of fresh oranges. If, after the BFS, there are still fresh oranges remaining, it's impossible to rot them all.

• Return Minutes: The number of levels traversed in the BFS (minutes) is the answer.

• Runtime Complexity: O(m n), Storage Complexity: O(m n) (due to the queue potentially holding all cells in the grid in the worst case).

Code

    from collections import deque

def oranges_rotting(grid):
    """
    Calculates the minimum minutes until all fresh oranges are rotten.

    Args:
        grid: A 2D list of integers representing the grid of oranges.

    Returns:
        The minimum number of minutes, or -1 if impossible.
    """

    rows, cols = len(grid), len(grid[0])
    fresh_oranges = 0
    rotten_oranges = deque()

    # Initialize the count of fresh oranges and the queue of rotten oranges
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                fresh_oranges += 1
            elif grid[r][c] == 2:
                rotten_oranges.append((r, c))

    minutes = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Possible directions to rot adjacent oranges

    while rotten_oranges and fresh_oranges > 0:
        minutes += 1
        for _ in range(len(rotten_oranges)):
            row, col = rotten_oranges.popleft()

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

                if (0 <= new_row < rows and
                        0 <= new_col < cols and
                        grid[new_row][new_col] == 1):
                    grid[new_row][new_col] = 2
                    fresh_oranges -= 1
                    rotten_oranges.append((new_row, new_col))

    if fresh_oranges == 0:
        return minutes
    else:
        return -1