Rotten Orange Grid Traversal Algorithm | 2D Array | Graph Traversal Algo

You are given an m x n grid where each cell can have one of three values:

1. 0 representing an empty cell,
2. 1 representing a fresh orange, or
3. 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent 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.

Situation:

1. given m *n grid
2. each cell in the grid can have 0 ,1, 2
3. 0 : empty cell
4. 1 : fresh orange
5. 2 : rotten orange.
6. Every min, any fresh orange that is 4 directionally adjacent to a rotten orange becomes rotten. 

         1   
       1 2. 1
         1

         2
       2 2 2
         2

        Task:

1.       Return the minimum number of mins, that must elapseuntil no cell has a fresh orange.
2. eturn -1 if impossible

          2. 0  0
          2  0  1
          0  0  0
           

          return -1

        Action:

1. One i can conclude is that, since every minue, a level is traversed/rotten. it's a level order traversal.
2. up , right, down , left gets rotten every min, ; use BFS to traverse
3. we will first find out all the position where we have rotten orange
4.  we will know the total and the position of rotten oranges as well as total fresh oranges
5.  then we will start the bfs traversal, with level order from each rotten orange for each rotten orange
6. if the number of oranges rotten is equal to the fresh oranges we will return the value else -1

var orangesRotting = function(grid) {
  
  const directions = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1]
  ]
  function inBound(value, max){
    return -1 < value && value < max
  }

A Normal BFS:

  function bfs(){
    let queue = []
    queue.push([0, 0])
    while(queue.length){
      const [row, col] = queue.shift()
      for(let [dirRow, dirCol] of dir){
          let newRow = row + dirRow
          let newCol = col + dirCol
          if(inBound(newRow, grid[0].length) && inBound(newCol, grid[1].length)){
            queue.push([newRow, newCol])            
          }
      }
    }  
  }

  function bfsLevel(queue){
    let min = 0
    let totalRotten = 0
       
    while(0 < queue.length){
      let queueSize = queue.length
      let count = 0
      while( count < queueSize){
        const [row, col] = queue.shift()
         
       for(let [dirRow, dirCol] of directions){
          let newRow = row + dirRow
          let newCol = col + dirCol
          if(inBound(newRow, grid.length) 
            && inBound(newCol, grid[0].length) 
            && grid[newRow][newCol] === 1){
            grid[newRow][newCol] = 2
            totalRotten++
            queue.push([newRow, newCol])            
          }
      }
        count++
      }
      if(queue.length){
        min++
      }
    }
     
    return {min, totalRotten}
  }
   

  const queue = []
  let fresh = 0
  for(let i = 0; i < grid.length; i++){
    for(let j = 0; j < grid[0].length; j++){
      if(grid[i][j] === 2){
          queue.push([i, j])
      }
      if(grid[i][j] === 1){
        fresh++
      }
    }
  }
  let {min, totalRotten} = bfsLevel(queue)
  return totalRotten === fresh ? min : -1
};

why is this line very important?

if(queue.length){
        min++
      }

The line if (queue.length) min++ is crucial in the bfsLevel function because it ensures that the min counter is only incremented when there are still oranges to process in the next level of the BFS traversal. Here's why it's important:

Explanation of the Code Logic

1. BFS Level Order Traversal:

• The BFS traversal processes the grid level by level, where each level represents one minute of time passing.
• At each level, all currently rotten oranges (2) infect their adjacent fresh oranges (1), turning them into rotten oranges.

1. Queue and Levels:

• The queue holds the positions of rotten oranges that are currently being processed.
• The queueSize variable tracks the number of rotten oranges at the current level.
• The inner while loop processes all rotten oranges at the current level and adds newly rotten oranges to the queue for the next level.

1. Incrementing min:

• After processing all rotten oranges at the current level, the min counter is incremented to represent the passage of one minute.
• However, the min counter should only be incremented if there are still oranges in the queue to process (i.e., if there are newly rotten oranges that will infect others in the next minute).

Why if (queue.length) min++ is Important

• Prevents Overcounting:
• If the queue is empty after processing a level, it means there are no more oranges to infect, and no further minutes need to be counted.
• Without this check, the min counter would be incremented even when no new infections occur, leading to an incorrect result.
• Accurate Time Tracking:
• The min counter represents the total time elapsed until no fresh oranges remain.
• By incrementing min only when there are still oranges to process, the code ensures that the final value of min accurately reflects the minimum time required.