Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
EDGE CASE
Input: grid = [[0,2]]
Output: 0Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For 2D-Array, common solution patterns include:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a queue data structure to keep track of the candidates that we need to visit during the process
1. Initialize a queue for breadth first search.
2. Iterate over the entire grid and add all the rotten oranges in the queue and also keep counting the number of fresh oranges.
3. If the number of fresh oranges is zero then we can directly return zero.
4. Otherwise, traverse the queue in level order fashion and add all the adjacent fresh oranges in the queue and decrement the count of fresh oranges by 1 each time. When we add a fresh orange in the queue, we mark it as rotten so that it is not added multiple times.
5. If after one complete traversal of a level, the queue is not empty, then increase the minutes by one.
6. Repeat this process until we have no more rotten oranges.
7. If the number of fresh oranges after the entire process is still not zero, then return -1 indicating that itโs impossible to rot all the oranges.
8. Else return the time required to rot all the oranges.โ ๏ธ Common Mistakes
Implement the code to solve the algorithm.
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
queue = deque()
# Step 1). build the initial set of rotten oranges
fresh_oranges = 0
ROWS, COLS = len(grid), len(grid[0])
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh_oranges += 1
# Mark the round / level, _i.e_ the ticker of timestamp
queue.append((-1, -1))
# Step 2). start the rotting process via BFS
minutes_elapsed = -1
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while queue:
row, col = queue.popleft()
if row == -1:
# We finish one round of processing
minutes_elapsed += 1
if queue: # to avoid the endless loop
queue.append((-1, -1))
else:
# this is a rotten orange
# then it would contaminate its neighbors
for d in directions:
neighbor_row, neighbor_col = row + d[0], col + d[1]
if ROWS > neighbor_row >= 0 and COLS > neighbor_col >= 0:
if grid[neighbor_row][neighbor_col] == 1:
# this orange would be contaminated
grid[neighbor_row][neighbor_col] = 2
fresh_oranges -= 1
# this orange would then contaminate other oranges
queue.append((neighbor_row, neighbor_col))
# return elapsed minutes if no fresh orange left
return minutes_elapsed if fresh_oranges == 0 else -1class Solution {
public int orangesRotting(int[][] grid) {
Queue<Pair<Integer, Integer>> queue = new ArrayDeque();
// Step 1). build the initial set of rotten oranges
int freshOranges = 0;
int ROWS = grid.length, COLS = grid[0].length;
for (int r = 0; r < ROWS; ++r)
for (int c = 0; c < COLS; ++c)
if (grid[r][c] == 2)
queue.offer(new Pair(r, c));
else if (grid[r][c] == 1)
freshOranges++;
// Mark the round / level, _i.e_ the ticker of timestamp
queue.offer(new Pair(-1, -1));
// Step 2). start the rotting process via BFS
int minutesElapsed = -1;
int[][] directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
while (!queue.isEmpty()) {
Pair<Integer, Integer> p = queue.poll();
int row = p.getKey();
int col = p.getValue();
if (row == -1) {
// We finish one round of processing
minutesElapsed++;
// to avoid the endless loop
if (!queue.isEmpty())
queue.offer(new Pair(-1, -1));
} else {
// this is a rotten orange
// then it would contaminate its neighbors
for (int[] d : directions) {
int neighborRow = row + d[0];
int neighborCol = col + d[1];
if (neighborRow >= 0 && neighborRow < ROWS &&
neighborCol >= 0 && neighborCol < COLS) {
if (grid[neighborRow][neighborCol] == 1) {
// this orange would be contaminated
grid[neighborRow][neighborCol] = 2;
freshOranges--;
// this orange would then contaminate other oranges
queue.offer(new Pair(neighborRow, neighborCol));
}
}
}
}
}
// return elapsed minutes if no fresh orange left
return freshOranges == 0 ? minutesElapsed : -1;
}
}Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N represents the number of rows in 2D-array.
Assume M represents the number of columns in 2D-array.
