Rotten Oranges
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.graphs;
/* * ============================================================================================ * PROBLEM: Rotten Oranges * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given an N x M grid: * - 0: Empty cell * - 1: Fresh orange * - 2: Rotten orange * Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange * becomes rotten. Return the minimum time to rot all oranges. If impossible, return -1. * * --------------------- * 2. Logical Breakdown * --------------------- * This is a Multi-Source BFS problem. * * 1. Initialization: * - Add all initial rotten oranges (value 2) to a Queue with time = 0. * - Count total fresh oranges. * 2. BFS Process: * - While Queue is not empty: * - Pop (r, c, current_time). * - Check 4 neighbors. If neighbor is fresh (1): * - Mark neighbor as rotten (2). * - Decrement fresh count. * - Enqueue neighbor with time = current_time + 1. * 3. Conclusion: * - If fresh count == 0, return current_time. * - Else, return -1. * * --------------------- * 3. Complexity * --------------------- * Time: O(N * M) - Every cell is visited once. * Space: O(N * M) - Queue size in worst case. * ============================================================================================ / public class RottenOranges { public int solve(int[][] A) { // TODO: Implement solution return 0; } }