Rotten Oranges
BFS & DFS Problems DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Rotten Oranges Problem: Minimum Time to Rot All Oranges in a Grid, Queue, Breadth-First Search, Graph Traversal, Matrices, Two-dimensional Array Traversal, Time Complexity, Space Complexity, time complexity analysis, queue, grid traversal, bfs, Graph Traversal (BFS), Grid as a Graph.
Problem: Rotting Oranges 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. 2 representing a rotten orange. Every minute, any fresh orange that is 4 directionally adjacent (up, down, left, right) 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. Input Format: The input consists of a 2D integer array grid representing the state of the oranges. Output Format: Return an integer, the minimum number of minutes, or 1 if it's impossible. Examples: Example 1: Input: Output: Explanation: The orange at (0, 1) initially fresh will never rot because it has no rotten neighbors and no path to any rotten orange. Example 2: Input: Output: Explanation: Initially, rotten oranges are at (0,0). Minute 1: (0,1) and (1,0) become rotten. Minute 2: (0,2) and (1,1) become rotten. Minute 3: (2,1) becomes rotten. Minute 4: (2,2) becomes rotten. All fresh oranges are rotten in 4 minutes.