# LeetCode: Rotting Oranges in C#

https://leetcode.com/problems/rotting-oranges/
Please review for coding style in 40 minutes job interview.

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Example 2:

Input: [[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: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.


Note:

1. 1 <= grid.length <= 10
2. 1 <= grid.length <= 10
3. grid[i][j] is only 0, 1, or 2.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.Serialization.Formatters;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace GraphsQuestions
{

/// <summary>
/// https://leetcode.com/problems/rotting-oranges/
/// </summary>
[TestClass]
public class RottingOrangesTest
{
[TestMethod]
public void ExampleTest()
{
int[][] grid =
{
new []{2, 1, 1 },
new []{1, 1, 0},
new []{0, 1, 1}
};
Assert.AreEqual(4, RottingOrangesClass.OrangesRotting(grid));
}
[TestMethod]
{
int[][] grid =
{
new []{2, 1, 1 },
new []{0, 1, 1},
new []{1, 0, 1}
};
Assert.AreEqual(-1, RottingOrangesClass.OrangesRotting(grid));
}

}

public class RottingOrangesClass
{

/// <summary>
/// we will use BFS and not DFS because we can move in one step to all of the directions.
/// </summary>
/// <param name="grid"></param>
/// <returns></returns>
public static int OrangesRotting(int[][] grid)
{
if (grid == null || grid.Length == 0)
{
return 0;
}

int countFreshOranges = 0;
Queue<int[]> Q = new Queue<int[]>();
for (int row = 0; row < grid.Length; row++)
{
for (int col = 0; col < grid.Length; col++)
{
if (grid[row][col] == 2)
{
Q.Enqueue(new int[] { row, col }); // we save the rotten oranges
}
else if (grid[row][col] == 1)
{
countFreshOranges++; // we count the fresh oranges
}
}
}

if (countFreshOranges == 0)
{
return 0;
}

int count = 0;
while (Q.Count > 0)
{
count++;
int size = Q.Count;
for (int i = 0; i < size; i++)
{
int[] point = Q.Dequeue();

//try all directions
int x = point;
int y = point;
countFreshOranges = TryDirection(grid, x + 1, y, Q, countFreshOranges);
countFreshOranges = TryDirection(grid, x - 1, y, Q, countFreshOranges);
countFreshOranges = TryDirection(grid, x, y + 1, Q, countFreshOranges);
countFreshOranges = TryDirection(grid, x, y - 1, Q, countFreshOranges);

}
}

if (countFreshOranges == 0)
{
return count - 1;
}

return -1;
}

private static int TryDirection(int[][] grid, int x, int y, Queue<int[]> Q, int countFreshOranges)
{
//check out of bounds
//also check for no orange or already rotten
if (x < 0 || y < 0 || x >= grid.Length || y >= grid.Length || grid[x][y] == 2 || grid[x][y] == 0)
{
return countFreshOranges;
}

grid[x][y] = 2;
Q.Enqueue(new int[] { x, y });
countFreshOranges--;
return countFreshOranges;
}
}
}


In your

private static int TryDirection(int[][] grid, int x, int y, Queue<int[]> Q, int countFreshOranges)


method I would invert the logic: If the given coordinate is valid and the field contains a fresh orange, then do something:

private static int TryDirection(int[][] grid, int x, int y, Queue<int[]> Q, int countFreshOranges)
{
if (x >= 0 && y >= 0 && x < grid.Length && y < grid.Length && grid[x][y] == 1)
{
grid[x][y] = 2;
Q.Enqueue(new int[] { x, y });
countFreshOranges--;
}
return countFreshOranges;
}


That is shorter and easier to understand.

The while loop in

public static int OrangesRotting(int[][] grid)


does one iteration more than is necessary: When all fresh oranges have rotten, another loop iteration is needed to empty the queue. That is also the reason why count - 1 is returned in the success case. It becomes clearer if both countFreshOranges and the queue are checked in the while condition:

int count = 0;
while (countFreshOranges > 0 && Q.Count > 0)
{
count++;
// ...
}
return countFreshOranges == 0 ? count : -1;


That makes also the preceding check

if (countFreshOranges == 0)
{
return 0;
}


obsolete.

Some more thoughts:

• Use an enum type (with values Free, Fresh and Rotten) instead of the integer constants 0, 1, 2, so that the code becomes more self-explaining.
• Instead of pushing int[] onto the queue, a tuple with two elements, or a struct with two members x and y would be sufficient.
• Q is too short as a variable name, it does not tell what the variable is used for.