2
\$\begingroup\$

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[0].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]
        public void BadExampleTest()
        {
            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.
        /// not one by one and in this way we will get the best result
        /// </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[0].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[0];
                    int y = point[1];
                    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[0].Length || grid[x][y] == 2 || grid[x][y] == 0)
            {
                return countFreshOranges;
            }

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

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[0].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.
\$\endgroup\$
  • \$\begingroup\$ thanks for the review \$\endgroup\$ – Gilad Oct 4 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.