25 Questions
Graphs:
1. Clone Graph
2. Course Schedule
3. 01 Matrix
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two cells sharing a common edge is 1.
Example 1:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]]
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length; // Number of rows
int n = mat[0].length; // Number of columns
Queue<int[]> queue = new LinkedList<>(); // Queue to perform BFS
// Initialize matrix:
// Add all 0s to the queue and mark all 1s as unvisited (-1)
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(mat[i][j] == 0){
// Add coordinates of 0s to the queue as starting points
queue.add(new int[]{i, j});
} else {
// Mark 1s as -1 to indicate they haven't been processed yet
mat[i][j] = -1;
}
}
}
// Directions to move in the matrix: up, down, left, right
int[][] directions = new int[][]{
{-1, 0}, // Up
{1, 0}, // Down
{0, -1}, // Left
{0, 1} // Right
};
// Perform BFS from all 0s simultaneously
while(!queue.isEmpty()){
int[] curr = queue.poll(); // Current cell coordinates
int currRow = curr[0];
int currCol = curr[1];
// Explore all four directions
for(int[] direction : directions){
int row = currRow + direction[0];
int col = currCol + direction[1];
// Check bounds and whether the cell is unvisited
if(row < 0 || row >= m || col < 0 || col >= n || mat[row][col] != -1){
continue; // Skip invalid or already visited cells
}
// Update the distance and enqueue the cell
mat[row][col] = mat[currRow][currCol] + 1;
queue.add(new int[]{row, col});
}
}
// Return the updated matrix with minimum distances to 0
return mat;
}
}