Solve grid compromise spread with BFS
LyftSoftware Engineer · OnsiteLast updated
This question evaluates proficiency in graph traversal and grid-based simulation, specifically multi-source breadth-first search, state propagation modeling, and algorithmic complexity analysis within the Coding & Algorithms domain, emphasizing practical application of implementation and reasoning.
You are given an m×n grid representing a data center: 0 = empty rack, 1 = secure server, 2 = compromised server. Each minute, any secure server that is orthogonally adjacent (up/down/left/right) to a compromised server becomes compromised. Return the minimum number of minutes to compromise all secure servers, or -1 if some remain forever secure. Describe your algorithm, explain why it is correct, and state time and space complexity. Include how you would handle multiple initial compromised sources and early termination.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.