Maximum time to rot all oranges


  • 1
    A

    You are given a matrix of dimensions m*n where each cell in the matrix can have values 0,1 or 2 which has the following meaning :

    0:empty cell

    1:cells have fresh oranges

    2:cells have rotten oranges

    So we have to determine what is the minimum time required so that all the oranges will be rotten,assuming it takes one second to rot the immediate neighbours. A rotten orange at index [i,j] can rot other fresh orange at indexes [i+1,j] ,[i,j+1] ,[i-1,j] ,[i,j-1]. If it is impossible to rot every orange then simply return -1


  • -2
    D

    what is the initial arrangement of 0,1,2s in the matrix?


  • 0
    A

    The arrangement is not pre-defined. The solution should find out the time for any arrangement of 0,1,2s.


  • 0
    S

    A brute force solution is here. The time complexity is O(n^2m^2) which is really bad and I think it can be improved.
    Basically the idea is to keep on rotting the neighbors of a cell containing 2, one by one and counting the iterations. After reaching the maximum iterations of n
    m, if we still have oranges that aren't rot it means that there is no solution so return -1.enter code here

    GitHub Link: https://github.com/shivam-maharshi/Algorithms/blob/master/src/microsoft/MaxTimeToRotAllOranges.java

    {
    /**

    • You are given a matrix of dimensions m*n where each cell in the matrix can

    • have values 0,1 or 2 which has the following meaning: 0:empty cell. 1:cells

    • have fresh oranges. 2:cells have rotten oranges. So we have to determine what

    • is the minimum time required so that all the oranges will be rotten,assuming

    • it takes one second to rot the immediate neighbors. A rotten orange at index

    • [i,j] can rot other fresh orange at indexes [i+1,j] ,[i,j+1] ,[i-1,j]

    • ,[i,j-1]. If it is impossible to rot every orange then simply return -1

    • Link: https://leetcode.com/discuss/50141/maximum-time-to-rot-all-oranges

    • @author shivam.maharshi
      */
      public class MaxTimeToRotAllOranges {

      private static int[] xa = new int[] { 0, 0, -1, 1 };
      private static int[] ya = new int[] { -1, 1, 0, 0 };

      /*

      • Time Complexity: O(n^2*m^2). Which is really bad and can be improved.
        /
        public static int getTime(int[][] a) {
        int count = 0;
        // Scope of improving time complexity here from O(n
        m).
        while (count < a.length * a[0].length) {
        if (allRotten(a))
        return count;
        count++;
        Set<Cell> s = rotNeighbors(a);
        for (Cell c : s) {
        a[c.x][c.y] = 2;
        }
        }
        return -1;
        }

      // Time Complexity: O(n*m)
      private static Set<Cell> rotNeighbors(int[][] a) {
      Set<Cell> list = new HashSet<>();
      for (int x = 0; x < a.length; x++) {
      for (int y = 0; y < a[0].length; y++) {
      if (a[x][y] == 2) {
      for (int k = 0; k < 4; k++) {
      int nextX = x + xa[k];
      int nextY = y + ya[k];
      if (isValid(a, nextX, nextY) && a[nextX][nextY] == 1) {
      list.add(new Cell(nextX, nextY));
      }
      }
      }
      }
      }
      return list;
      }

      private static boolean isValid(int[][] a, int x, int y) {
      return (x >= 0 && y >= 0 && x < a.length && y < a[0].length);
      }

      private static boolean allRotten(int[][] a) {
      for (int i = 0; i < a.length; i++) {
      for (int j = 0; j < a[0].length; j++) {
      if (a[i][j] == 1)
      return false;
      }
      }
      return true;
      }

      public static void main(String[] args) {
      int[][] a = new int[][] { { 1, 1, 2, 2 }, { 1, 2, 2, 2 }, { 2, 2, 0, 0 }, { 2, 2, 0, 1 } };
      System.out.println(getTime(a));
      }

    }

    class Cell {

    int x;
    int y;
    
    public Cell(int x, int y) {
    	this.x = x;
    	this.y = y;
    }
    

    }


  • 0

    I'm not sure what @aceofspades means by maximum time or minimum time (in the title it says maximum time and in the description it says we have to determine the minimum time). What I understand is that find the time that till all fresh oranges get rotten (if possible).

    Complexity is O(M x N) because we only visit each cell once. Fresh oranges that got infected will be visited twice.

    int timeToRot = 0;
    	public void problemTimeToRotOrange() {
    		int[][] farm = new int[][] {{1, 1, 1, 1, 0},
    									{0, 1, 0, 1, 1},
    									{2, 1, 1, 0, 2},
    									{2, 1, 1, 0, 0}};
    //		int[][] farm = new int[][] {{1, 0, 1, 1, 0},
    //									{0, 1, 0, 1, 1},
    //									{2, 1, 1, 0, 2},
    //									{2, 1, 1, 0, 0}};
    		timeToRotFarm(farm);
    //		for(int i = 0; i < farm.length; i++) {
    //			for(int j = 0; j < farm[0].length; j++)
    //				System.out.print(farm[i][j] + " ");
    //			System.out.println();
    //		}
    		for(int i = 0; i < farm.length; i++) {
    			for(int j = 0; j < farm[0].length; j++) {
    				if(farm[i][j] == 1) {
    					timeToRot = -1;
    					break;
    				}
    			}
    		}
            System.out.println(timeToRot);
    	}
    
    	private void timeToRotFarm(int[][] farm) {
    		boolean[][] visited = new boolean[farm.length][farm[0].length];
    		for(int i = 0; i < farm.length; i++) {
    			for(int j = 0; j < farm[0].length; j++) {
    				if(farm[i][j] == 2)
    					rotCrop(farm, i, j, visited);
    			}
    		}
    	}
    
    	private void rotCrop(int[][] farm, int i, int j, boolean[][] visited) {
    		if(i < 0 || i == farm.length || j < 0 || j == farm[0].length || farm[i][j] == 0 || visited[i][j])
    			return;
    		if(farm[i][j] == 2) {
    			visited[i][j] = true;
    			// move north
    			rotCrop(farm, i - 1, j, visited);
    			// move east
    			rotCrop(farm, i, j + 1, visited);
    			// move south
    			rotCrop(farm, i + 1, j, visited);
    			// move west
    			rotCrop(farm, i, j - 1, visited);
    			return;
    		} else if(farm[i][j] == 1){
    			// farm[i][j] = 1, it's fresh so infect it
    			farm[i][j] = 2;
    			timeToRot++;
    			rotCrop(farm, i, j, visited);
    		}
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.