How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Lyft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Lyft during technical interviews.

Solve grid compromise spread with BFS

Quick Overview

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.

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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.

Quick Answer: 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.

Given an m x n grid representing a data center, 0 means empty rack, 1 means secure server, and 2 means compromised server. Every minute, any secure server that is orthogonally adjacent to a compromised server becomes compromised. Return the minimum number of minutes needed to compromise all secure servers, or -1 if some servers can never be compromised. If there are no secure servers initially, return 0. In your explanation, describe your algorithm, why it is correct, its time and space complexity, and how it handles multiple initial compromised sources and early termination.

Constraints

0 <= m, n <= 200
grid is rectangular
grid[i][j] is one of 0, 1, or 2

Examples

Input: [[2,1,1],[1,1,0],[0,1,1]]

Expected Output: 4

Explanation: The compromise spreads outward level by level and reaches the last secure server after 4 minutes.

Input: [[2,1,1],[0,1,1],[1,0,1]]

Expected Output: -1

Explanation: The secure server in the bottom-left region can never be reached because empty racks block all paths.

Input: [[0,2]]

Expected Output: 0

Explanation: There are no secure servers at the start, so no time is needed.

Input: []

Expected Output: 0

Explanation: An empty grid has no secure servers to compromise.

Input: [[2,1,1],[1,1,1],[1,1,2]]

Expected Output: 2

Explanation: Two initial compromised servers spread simultaneously, so all secure servers are compromised in 2 minutes.

Input: [[1]]

Expected Output: -1

Explanation: There is a secure server but no compromised server to start the spread.

Solution

from collections import deque

def solution(grid):
    # Multi-source BFS: every compromised server starts spreading at minute 0.
    # Each BFS layer represents one minute of spread.
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    queue = deque()
    secure = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                secure += 1

    if secure == 0:
        return 0

    minutes = 0
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    while queue and secure > 0:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    secure -= 1
                    queue.append((nr, nc))
        minutes += 1

        # Early termination: BFS explores states in increasing time order,
        # so the first minute when secure becomes 0 is the minimum answer.
        if secure == 0:
            return minutes

    return -1

Time complexity: O(m * n). Space complexity: O(m * n).

Hints

Think of all initially compromised servers as starting points in the same BFS queue.
Track how many secure servers remain; once that count reaches 0, you can return immediately.

Quick Overview