994 rotting oranges - March 30, 2020 10:00 PM mock interview - interviewee wrote bug-free code

994RottingOranges.java

class Solution {
  public static void main(String[] args) {   
    
    Solution s = new Solution();    
    
    int[] nums2 = {2, 1};
    
    int[][] grid = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};

    System.out.println(s.rottenOrange(grid));
  }
  
  public int rottenOrange(int[][] grid) {
    int h = grid.length;
    
    if(h == 0) {
      return -1;
    }
    
    int w = grid[0].length;
    
    int[] directionX = {0, 0 , -1, 1};
    int[] directionY = {1, -1 , 0, 0};
    
    Queue<Integer> queue = new LinkedList<>(); // x, y -> x * w + y 
    for(int i = 0; i < h; i++) { // height
      for(int j = 0; j < w; j++) {  // width
        if(grid[i][j] == 2) {
          queue.offer(i * w + j); // [i,j] -> i * w + j, integer 
        }
      }
    }
    
    int mins = 0;
    while(!queue.isEmpty()) {
      int size = queue.size();
      // update mins
      mins++;
      for(int i = 0; i < size; i++) {
        int cur = queue.poll();
        // 0 1 2 * * * * * * *
        // 3 4 5
        // 6 7 8 -> [0, 1, 2, 3, 4, 5, 6, 7, 8] -> row/ col number -> 0 - 8 
        // x * h + y <- x * (w + h) -> less error-prone -> out-of-range - which line 
        // cur = x * w + y
        // x = cur / w;
        // y = cur % w;
        int x = cur / w;  // divide - x = cur/ (w + h)
        int y = cur % w; //           y = cur % (w + h) 
        
        for(int j = 0; j < 4; j++) {
          int nextX = x + directionX[j];
          int nextY = y + directionY[j];
          if(inbound(nextX, nextY, grid)) {
            if(grid[nextX][nextY] == 1) {  // fresh -> 
              queue.offer(nextX * w + nextY);// add just-turn-rotten  
              grid[nextX][nextY] = 2;
            }
          }
        }
      }      
    }   
    
    for(int i = 0; i < h; i++) {
      for(int j = 0; j < w; j++) {
        if(grid[i][j] == 1) { // fresh orange 
          return -1;
        }
      }
    }
    
    if(mins == 0) { // 
      return 0;
    }
    
    return mins - 1;
  }
  
  public boolean inbound(int x, int y, int[][] grid) {
    int h = grid.length;
    if(h == 0) {
      return false;
    }
    
    int w = grid[0].length;    
    
    // x >=0 
    return x > -1 && x < h && y > -1 && y < w;
    /*
    if(x > -1 && x < h && y > -1 && y < w) {
      return true;
    }
    return false;*/
  }   
}