The Meeting Place Sequel - Amazon Top Interview Questions

                        Solution in C++ :

bool isSafe(vector<vector<int>> &matrix, int r, int c) {
    int m = matrix.size();
    int n = matrix[0].size();

    return (r >= 0 && c >= 0 && r < m && c < n && matrix[r][c] != 1);
}

void bfs(vector<vector<int>> &matrix, vector<vector<int>> &answer, int row, int col) {
    int m = matrix.size();
    int n = matrix[0].size();

    int hor[4] = {-1, 1, 0, 0};
    int ver[4] = {0, 0, 1, -1};

    vector<vector<bool>> visited(m, vector<bool>(n, false));
    queue<vector<int>> nodes;

    nodes.push({row, col, 0});
    visited[row][col] = true;

    while (!nodes.empty()) {
        int curRow = nodes.front()[0];
        int curCol = nodes.front()[1];
        int level = nodes.front()[2];
        nodes.pop();

        answer[curRow][curCol] = max(answer[curRow][curCol], level);

        for (int i = 0; i < 4; i++) {
            int newRow = curRow + hor[i];
            int newCol = curCol + ver[i];

            if (isSafe(matrix, newRow, newCol) && !visited[newRow][newCol]) {
                visited[newRow][newCol] = true;
                nodes.push({newRow, newCol, level + 1});
            }
        }
    }

    return;
}

int solve(vector<vector<int>> &matrix) {
    int m = matrix.size();
    int n = matrix[0].size();

    vector<vector<int>> answer(m, vector<int>(n, -1));

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) answer[i][j] = 31;
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 2) {
                bfs(matrix, answer, i, j);
            }
        }
    }

    int minTime = 31;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (answer[i][j] != -1) minTime = min(minTime, answer[i][j]);
        }
    }

    return (minTime == 31 ? 0 : minTime);
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    int dis[][][];
    public int solve(int[][] mat) {
        int res = Integer.MAX_VALUE;
        int n = mat.length, m = mat[0].length;
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 2) {
                    list.add(new int[] {i, j});
                }
            }
        }
        dis = new int[n][m][list.size()];
        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis[0].length; j++) {
                Arrays.fill(dis[i][j], -1);
            }
        }

        for (int i = 0; i < list.size(); i++) {
            bfs(mat, list.get(i)[0], list.get(i)[1], i);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int sum = 0;
                for (int k = 0; k < dis[i][j].length; k++) {
                    if (dis[i][j][k] == -1) {
                        sum = Integer.MAX_VALUE;
                        break;
                    } else {
                        sum = Math.max(sum, dis[i][j][k]);
                    }
                }
                res = Math.min(res, sum);
            }
        }
        return res;
    }

    public void bfs(int mat[][], int sr, int sc, int index) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {sr, sc, 0});
        dis[sr][sc][index] = 0;
        while (q.size() != 0) {
            int pair[] = q.poll();
            int r = pair[0], c = pair[1], level = pair[2];
            add(q, mat, r + 1, c, level + 1, index);
            add(q, mat, r - 1, c, level + 1, index);
            add(q, mat, r, c + 1, level + 1, index);
            add(q, mat, r, c - 1, level + 1, index);
        }
    }

    public void add(Queue<int[]> q, int mat[][], int i, int j, int level, int index) {
        if (i < 0 || j < 0 || i >= mat.length || j >= mat[0].length)
            return;
        if (mat[i][j] == 1)
            return;
        if (dis[i][j][index] != -1)
            return;
        dis[i][j][index] = level;
        q.add(new int[] {i, j, level});
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, matrix):
        m, n = len(matrix), len(matrix[0])
        distGrid = [[float("inf") for _ in range(n)] for _ in range(m)]

        def bfs(i, j):
            queue = deque([(i, j, 0)])
            visited = [[False for _ in range(n)] for _ in range(m)]
            visited[i][j] = True
            while queue:
                x, y, dist = queue.popleft()
                if distGrid[x][y] == float("inf"):
                    distGrid[x][y] = 0
                distGrid[x][y] = max(distGrid[x][y], dist)
                for r, c in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if 0 <= r < m and 0 <= c < n and not visited[r][c] and matrix[r][c] != 1:
                        visited[r][c] = True
                        queue.append((r, c, dist + 1))

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 2:
                    bfs(i, j)

        res = min(min(row) for row in distGrid)
        return res if res != float("inf") else 0