Problem Explanation

You are given a matrix (2D array) that consists of 0s and 1s. Your task is to find the shortest distance from each cell to the nearest cell that contains a 0. If a cell already contains a 0, its distance from itself is 0. Two cells are considered adjacent if they share a common edge, i.e., they are either horizontally or vertically adjacent.

For example, consider the following 3x3 matrix. `` Input: [[0,0,0], [0,1,0], [1,1,1]]

Output: [[0,0,0], [0,1,0], [1,2,1]]

1
2
3Here, every cell contains its distance from the nearest cell having a value of 0. For example, the cell in the 3rd row, 3rd column has a distance of '1' because its nearest 0 is at the cell (3rd row, 2nd column), and the distance between these two cells is 1.
4
5Similarly, the cell in the 3rd row, 2nd column has its nearest zero in multiple locations, such as at the cells (2nd row, 2nd column) or (3rd row, 1st column) etc.
6But the minimum distance among these is considered, which is '2' (i.e., 2nd row, 2nd column).
7
8# Solution approach
9
10To solve this problem, we can use breadth-first search (BFS) algorithm starting from each cell that contains a 0. BFS enables us to visit every accessible cell with the shortest path first, which ensures that once we have found a 0 from a cell, it is guaranteed to be the nearest one.
11
12The first step in this process is to create an empty queue and push every cell that contains a 0 into it. Then we start the BFS process.
13
14In each iteration of the BFS, we pop a cell from the queue and visit its four adjacent cells (up, down, left, right). If an adjacent cell has not been visited before and it contains a 1, we update its value to be the current cell's value plus 1, and then push it into the queue.
15
16This process continues until we have visited every accessible cell.
17
18Let's now move to the coding part.
19
20# Python Solution

python from collections import deque

class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: m, n = len(mat), len(mat[0]) dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] queue = deque() visited = set()

1    for i in range(m):
2        for j in range(n):
3             if mat[i][j] == 0:
4                queue.append((i, j))    
5                visited.add((i, j))
6
7     while queue:
8        x, y = queue.popleft()
9        for dx, dy in dirs:
10            nx, ny = x + dx, y + dy
11            if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
12                mat[nx][ny] = mat[x][y] + 1
13                queue.append((nx, ny))
14                visited.add((nx, ny))
15
16     return mat

1
2
3
4Instead of using a separate matrix to record whether a cell has been visited, we use a set 'visited' to hold the coordinates of those cells, to save some space. Then we use queue to process the cells level by level, with the goal of finding the nearest 0 for each cell. 
5
6# Java Solution

java class Solution { public int[][] updateMatrix(int[][] mat) { int m = mat.length, n = mat[0].length; int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

1    Queue<int[]> queue = new LinkedList<>();
2    
3    for (int i = 0; i < m; i++) {
4        for (int j = 0; j < n; j++) {
5            if (mat[i][j] == 0) {
6                queue.offer(new int[] { i, j });
7            } else {
8                mat[i][j] = m + n;
9            }
10        }
11    }
12    
13    while (!queue.isEmpty()) {
14        int[] cell = queue.poll();
15        for (int[] dir : dirs) {
16            int r = cell[0] + dir[0];
17            int c = cell[1] + dir[1];
18            if (r < 0 || r == m || c < 0 || c == n || mat[r][c] <= mat[cell[0]][cell[1]] + 1)
19                continue;
20            queue.add(new int[] { r, c });
21            mat[r][c] = mat[cell[0]][cell[1]] + 1;
22        }
23    }

return mat; } };

1
2
3
4The Java solution is very similar to the Python solution. It differs only in syntax and library function names.  Also, instead of directly using `set` to store visited points, it uses `mat[i][j] = m + n;` to mark that points will be visited soon.
5
6# JavaScript Solution

javascript var updateMatrix = function(mat) { const q = []; for(let i = 0; i < mat.length; i++){ for(let j = 0; j < mat[0].length; j++){ if(mat[i][j] === 1) mat[i][j] = Number.MAX_SAFE_INTEGER; else q.push([i, j]); } }

1while(q.length){
2    const [x, y] = q.shift();
3    
4    for(let [dx, dy] of [[-1, 0], [1, 0], [0, -1], [0, 1]]){
5        const nx = x + dx, ny = y + dy;
6        
7        if(nx < 0 || ny < 0 || nx == mat.length || ny == mat[0].length || mat[nx][ny] <= mat[x][y] + 1) 
8            continue;
9        
10        q.push([nx, ny]);
11        mat[nx][ny] = mat[x][y] + 1;
12    }
13}
14
15return mat;

};

1
2
3
4The Javascript version follows almost the same steps with the Python and Java versions but in JavaScript syntax.
5
6# C++ Solution

cpp class Solution { public: vector<vector> updateMatrix(vector<vector>& mat) { int m = mat.size(); int n = mat[0].size(); vector<vector> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

1    queue<pair<int, int>> q;
2    vector<vector<bool>> visited(m, vector<bool>(n));
3
4    for (int i = 0; i < m; ++i)
5        for (int j = 0; j < n; ++j)
6            if (mat[i][j] == 0) {
7                q.push({i, j});
8                visited[i][j] = true;
9            }
10
11    while (!q.empty()) {
12        int i = q.front().first, j = q.front().second;
13        q.pop();
14        for (int k = 0; k < 4; k++) {
15            int x = i + dirs[k][0], y = j + dirs[k][1];
16            if (x < 0 || x == m || y < 0 || y == n || visited[x][y]) 
17                continue;
18            mat[x][y] = mat[i][j] + 1;
19            q.push({x, y});
20            visited[x][y] = true;
21        }
22    }
23
24    return mat;
25}

};

1
2
3
4The C++ solution is very similar to the Java solution, with syntax differences.
5
6# C# Solution
7

csharp public class Solution { public int[][] UpdateMatrix(int[][] mat) { int m = mat.Length, n = mat[0].Length; int[][] dirs = new int[][] { new int[]{ 0, 1 }, new int[]{ 1, 0 }, new int[]{ 0, -1 }, new int[] { -1, 0 } };

1    Queue<int[]> queue = new Queue<int[]>();
2
3    for (int i = 0; i < m; i++) {
4        for (int j = 0; j < n; j++) {
5            if (mat[i][j] == 0)
6                queue.Enqueue(new int[] { i, j });
7            else 
8                mat[i][j] = int.MaxValue;
9        }
10    }
11
12    while (queue.Count>0) {
13        int[] cell = queue.Dequeue();
14        for (int i = 0; i < 4; i++) {
15            int newRow = cell[0] + dirs[i][0], newCol = cell[1] + dirs[i][1];
16            if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || mat[newRow][newCol] <= mat[cell[0]][cell[1]] + 1) 
17                continue;
18            queue.Enqueue(new int[] { newRow, newCol });
19            mat[newRow][newCol] = mat[cell[0]][cell[1]] + 1;
20        }
21    }
22    return mat;
23}

}

1
2
3
4Again, the C# solution is similar to the C++ and the Java solution, with slight differences in syntax and APIs used.
5
6By following this BFS approach, we can find the shortest distance of the nearest 0 for each cell in a very efficient way.The time complexity of the solution is O(M*N), where M and N are the number of rows and columns in the matrix respectively. This is because each cell in the matrix is visited at most once in the BFS traversal.
7
8The space complexity is also O(M*N) in the worst case. This is because the worst case for the number of elements that the queue will store happened when all points are in the queue together.
9
10In summary, BFS can be a very efficient algorithm to solve problems like this. Its good performance is due to the combination of revising the states of visited cells and the nature of the BFS traversal, which guarantees us to visit each cell with the minimum path cost first.
11
12This kind of problem is very common in graph traversal algorithms. So, having a good understanding of such problems will greatly benefit your problem-solving skills when dealing with similar problems. 
13
14Understanding the BFS, reusing the original grid as the visitation record, and the boundary condition are the key points to solve the problem. Also, remember that if you are not familiar with a programming language in which you need to implement a solution, you can refer to similar solutions in a familiar programming language and then translate the logic to the target language. 
15
16If the above solutions still confuse you, it is recommended to debug them step by step so you can understand how inputs are processed and transformed into outputs.
17
18Although coding is a more practical way to understand the problem-solving processes and implement the solutions, understanding the theories behind the code, like BFS in this case, is also very important to become a good problem solver. So, always try to spend some time on fundamental computer science theories.
19
20Also, it is of utmost importance to test your code on various test cases including corner cases, small input cases, and large input cases. This will help you identify if there are any logical errors in your approach or any test conditions that your code cannot handle. It will also help you to understand how efficient your code is. Always remember that writing code is important, but writing efficient and correct code is what matters the most in problem-solving.
21
22In conclusion, make sure to practice such problems regularly. It will not only help you learn different problem-solving techniques but also make you more comfortable in using them.