Compute minimum escape time in a grid

Q: Compute minimum escape time in a grid

This question evaluates a candidate's competence in graph traversal, shortest-path computation, and reachability analysis on grid-based representations.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a 2D floor plan grid. Each cell is one of:

. empty space (walkable)
# wall/blocked (not walkable)
P a person
E an exit

A person can move 1 step per minute to the 4-neighbors (up/down/left/right) through walkable cells. Multiple people can occupy the same cell at the same time (ignore collisions).

Task:

Determine whether every person can reach some exit.
If everyone can escape, return the minimum time until all people have escaped , assuming each person walks optimally (i.e., the maximum over people of their shortest-path distance to any exit).

If some person cannot reach any exit, return -1.

Explain an algorithm and its time/space complexity.

Compute minimum escape time in a grid

Quick Overview

Comments (0)