I like to read this solution as a small machine: keep the useful information, throw away the noise. For 994. Rotting Oranges, the solution in this repository is mainly a graph traversal solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal, two pointers.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are orangesRotting.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02In a given grid, each cell can have one of three values:
03
04the value 0 representing an empty cell;
05the value 1 representing a fresh orange;
06the value 2 representing a rotten orange.
07Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.
08
09Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.
10
11
12
13Example 1:
14
15
16
17Input: [[2,1,1],[1,1,0],[0,1,1]]
18Output: 4
19Example 2:
20
21Input: [[2,1,1],[0,1,1],[1,0,1]]
22Output: -1
23Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.
24Example 3:
25
26Input: [[0,2]]
27Output: 0
28Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.
29
30
31Note:
32
331 <= grid.length <= 10
341 <= grid[0].length <= 10
35grid[i][j] is only 0, 1, or 2.
36**/
37
38//Runtime: 12 ms, faster than 86.00% of C++ online submissions for Rotting Oranges.
39//Memory Usage: 10 MB, less than 99.48% of C++ online submissions for Rotting Oranges.
40class Solution {
41public:
42 int orangesRotting(vector<vector<int>>& grid) {
43 queue<vector<int>> q;
44 int minute = 0;
45 int levelCount = 0;
46 vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
47
48 for(int i = 0; i < grid.size(); i++){
49 for(int j = 0; j < grid[0].size(); j++){
50 if(grid[i][j] == 2){
51 q.push(vector<int> {i,j});
52 levelCount++;
53 visited[i][j] = true;
54 }
55 }
56 }
57
58 while(!q.empty()){
59 vector<int> cur = q.front();
60 int curi = cur[0], curj = cur[1];
61 q.pop();
62
63 grid[curi][curj] = 2;
64
65 // cout << curi << " " << curj << endl;
66
67 if(curi > 0 && grid[curi-1][curj] == 1 && !visited[curi-1][curj]){
68 q.push(vector<int> {curi-1, curj});
69 visited[curi-1][curj] = true;
70 }
71
72 if(curi < grid.size()-1 && grid[curi+1][curj] == 1 && !visited[curi+1][curj]){
73 q.push(vector<int> {curi+1, curj});
74 visited[curi+1][curj] = true;
75 }
76
77 if(curj > 0 && grid[curi][curj-1] == 1 && !visited[curi][curj-1]){
78 q.push(vector<int> {curi, curj-1});
79 visited[curi][curj-1] = true;
80 }
81
82 if(curj < grid[0].size()-1 && grid[curi][curj+1] == 1 && !visited[curi][curj+1]){
83 q.push(vector<int> {curi, curj+1});
84 visited[curi][curj+1] = true;
85 }
86
87 levelCount--;
88 if(levelCount == 0 && q.size() > 0){
89 levelCount = q.size();
90 minute++;
91 }
92 }
93
94 for(int i = 0; i < grid.size(); i++){
95 for(int j = 0; j < grid[0].size(); j++){
96 if(grid[i][j] == 1) return -1;
97 }
98 }
99
100 // cout << endl;
101
102 return minute;
103 }
104};
105
106/**
107Approach 1: Breadth-First Search
108**/
109
110/**
111Complexity Analysis
112
113Time Complexity: O(N)O(N), where NN is the number of cells in the grid.
114
115Space Complexity: O(N)O(N).
116**/
117
118/**
119class Solution {
120public:
121 vector<int> dr = {-1, 0, 1, 0};
122 vector<int> dc = {0, -1, 0, 1};
123
124 int orangesRotting(vector<vector<int>>& grid) {
125 int R = grid.size(), C = grid[0].size();
126
127 queue<vector<int>> q;
128 map<vector<int>, int> depth;
129 for(int r = 0; r < R; r++){
130 for(int c = 0; c < C; c++){
131 if(grid[r][c] == 2){
132 q.push(vector<int> {r,c});
133 depth[vector<int> {r,c}] = 0;
134 }
135 }
136 }
137
138 int ans = 0;
139 while(!q.empty()){
140 vector<int> rc = q.front();
141 q.pop();
142 int r = rc[0], c = rc[1];
143 for(int k = 0; k < 4; k++){
144 int nr = r + dr[k];
145 int nc = c + dc[k];
146 if(nr >= 0 && nr < R && nc >= 0 && nc < C && grid[nr][nc] == 1){
147 //visit(modify grid) and then push into queue
148 grid[nr][nc] = 2;
149 q.push(vector<int> {nr, nc});
150 ans = depth[vector<int> {nr,nc}] = depth[vector<int> {r,c}] + 1;
151 }
152 }
153 }
154
155 for(vector<int> row : grid){
156 for(int e : row){
157 if(e == 1) return -1;
158 }
159 }
160
161 return ans;
162 }
163};**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.