01 Matrix LeetCode solution in Java

1
class Solution {
2
  // BFS
3
  // We add all 0 to the queue in the 0th level of the BFS. From there, every subsequent pair of
4
  // indexes added would be 1 in the mat. THis way levels can represent the distance of a one from
5
  // the closest 0 to it.
6
  boolean visited[][];
7

8
  // Could also convert the indexes to a single number by mat[0].length * i + j.
9
  class Pair {
10
    int x;
11
    int y;
12

13
    Pair(int x, int y) {
14
      this.x = x;
15
      this.y = y;
16
    }
17
  }
18

19
  public int[][] updateMatrix(int[][] mat) {
20
    int level = 0;
21
    visited = new boolean[mat.length][mat[0].length];
22
    Queue<Pair> q = new ArrayDeque<>();
23

24
    // Addition of all pairs in mat that have 0.
25
    for (int i = 0; i < mat.length; i++) {
26
      for (int j = 0; j < mat[0].length; j++) {
27
        if (mat[i][j] == 0) {
28
          visited[i][j] = true;
29
          q.add(new Pair(i, j));
30
        }
31
      }
32
    }
33

34
    while (q.size() > 0) {
35
      int size = q.size();
36
      while (size-- > 0) {
37
        Pair p = q.remove();
38
        mat[p.x][p.y] = level;
39
        if (p.x > 0 && visited[p.x - 1][p.y] == false) {
40
          visited[p.x - 1][p.y] = true;
41
          q.add(new Pair(p.x - 1, p.y));
42
        }
43
        if (p.x < mat.length - 1 && visited[p.x + 1][p.y] == false) {
44
          visited[p.x + 1][p.y] = true;
45
          q.add(new Pair(p.x + 1, p.y));
46
        }
47
        if (p.y > 0 && visited[p.x][p.y - 1] == false) {
48
          visited[p.x][p.y - 1] = true;
49
          q.add(new Pair(p.x, p.y - 1));
50
        }
51
        if (p.y < mat[0].length - 1 && visited[p.x][p.y + 1] == false) {
52
          visited[p.x][p.y + 1] = true;
53
          q.add(new Pair(p.x, p.y + 1));
54
        }
55
      }
56
      level++;
57
    }
58

59
    return mat;
60
  }
61
}