Session 46: Graph 3

Original Session

Date: 06 March 2025

Topic: Graph

Concept: Breadth First Search (BFS)

Programs

1. 994. Rotting Oranges
   1. leetcode here

      public int orangesRotting(int[][] grid) {
              
              Queue<Pair<Integer, Integer>> queue = new LinkedList();
              int m = grid.length;
              int n = grid[0].length;
              int min = 0;
              int freshOranges = 0;
      
              for (int i=0; i<m; i++) {
      
                  for (int j=0; j<n; j++) {
      
                      if (grid[i][j] == 2) {
      
                          queue.add(new Pair(i, j));
                      } else if (grid[i][j] == 1) {
      
                          freshOranges ++;
                      }
                  }
              }
      
              if (freshOranges == 0) {
                  return 0;
              }
              if (queue.isEmpty()) {
                  return -1;
              }
      
              int [][] dirs = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
              while(!queue.isEmpty()) {
      
                  int size = queue.size();
                  for (int i=0; i<size; i++) {
      
                      Pair<Integer, Integer> item = queue.remove();
                      for (int[] dir: dirs) {
      
                          int pairM = item.getKey() + dir[0];
                          int pairN = item.getValue() + dir[1];
      
                          if (pairM >= 0 && pairN >= 0 
                              && pairM < m && pairN < n
                              && grid[pairM][pairN] == 1) {
      
                              grid[pairM][pairN] = 2;
                              freshOranges --;
                              Pair<Integer, Integer> pair = new Pair(pairM, pairN);
                              queue.add(pair);
                          }
                      }                
                  }
                  min++;
              }
      
              if (freshOranges == 0) {
                  return min - 1;
              }
              return -1;
          }

2. 542. 01 Matrix
   1. leetcode here

      public int[][] updateMatrix(int[][] mat) {
              
              int m = mat.length;
              int n = mat[0].length;
      
              Queue<int[]> queue = new LinkedList();
      
              int[][] dist = new int[m][n];
              for (int i=0; i<m; i++) {
                  Arrays.fill(dist[i], -1);
              }
      
              for (int i=0; i<m; i++) {
                  for (int j=0; j<n; j++) {
                      if (mat[i][j] == 0) {
                          queue.add(new int[] {i, j});
                          dist[i][j] = 0;
                      }
                  }            
              }
      
              int[][] dirs = { {0,-1}, {-1,0}, {0,1}, {1,0}};
              while (!queue.isEmpty()) {
      
                  int[] item = queue.remove();
                  int x = item[0];
                  int y = item[1];
      
                  for (int[] dir: dirs) {
      
                      int newX = x + dir[0];
                      int newY = y + dir[1];
      
                      if (newX >= 0 && newY >= 0 
                          && newX < m && newY < n
                          && dist[newX][newY] == -1) {
      
                              dist[newX][newY] = 1 + dist[x][y];
                              queue.add(new int[] {newX, newY});
                          }
                  }
              }
      
              return dist;
          }

3. 841. Keys and Rooms
   1. leetcode here

      public boolean canVisitAllRooms(List<List<Integer>> rooms) {
              
              boolean[] visited = new boolean[rooms.size()];
              Queue<Integer> q = new LinkedList();
              q.add(0);
              
              while(!q.isEmpty()) {
                  
                  int vertex = q.remove();
                  if (visited[vertex]) {
                      continue;
                  }
                  
                  visited[vertex] = true;
                  List<Integer> vertices = rooms.get(vertex);
                  for(Integer i: vertices){
                      q.add(i);
                  }
              }
              
              for (boolean val: visited) {
                  if (val == false) {
                      return false;
                  }
              }
              return true;
          }