Minimum Cells to Bridge a Magic Grid
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Minimum Cells to Bridge a Magic Grid
You are given a magic grid `runes` with `rows` rows and `cols` columns. Each cell is one of three values:
- `0` — an empty cell.
- `1` — a charged rune already placed in the cell.
- `2` — a forbidden cell. A forbidden cell can never hold a rune and can never be traversed.
A spell is **castable** when magic can flow continuously from the **top edge** of the grid to the **bottom edge** of the grid through charged runes. Concretely, magic flows between two cells only if they are charged (value `1`) and are directly adjacent in one of the **four cardinal directions** (up, down, left, right — never diagonally). The top edge is "reached" if any charged cell in row `0` is connected to the magic flow; the bottom edge is "reached" if any charged cell in row `rows - 1` is connected to the magic flow. The spell is castable if there exists a path of 4-directionally adjacent charged cells that starts in row `0` and ends in row `rows - 1`.
You may **charge** additional empty cells (turn a `0` into a `1`). You may not change forbidden cells (`2`) and you may not place a rune on a forbidden cell. Charging an empty cell costs `1` rune.
Return the **minimum number of empty cells you must charge** so that the spell becomes castable, or `-1` if it is impossible (no path from the top edge to the bottom edge can be formed because every candidate route is blocked by forbidden cells).
If the grid is already castable with the runes that are present, the answer is `0`.
## Examples
**Example 1**
```
runes = [
[1, 0, 0],
[0, 0, 0],
[0, 0, 1]
]
```
Output: `2`
Explanation: The minimum solution is to charge cells `(1,0)` and `(2,0)`. This creates the path `(0,0) -> (1,0) -> (2,0)`, which starts in row `0` (at the already-charged rune `(0,0)`) and ends in row `2` (the bottom row). Only `2` empty cells need to be charged.
**Example 2**
```
runes = [
[1, 1, 1],
[2, 2, 1],
[1, 1, 1]
]
```
Output: `0`
Explanation: A charged path already exists from row `0` to row `2` (for example `(0,2) -> (1,2) -> (2,2)`), so no new runes are needed.
**Example 3**
```
runes = [
[0, 2, 0],
[2, 2, 2],
[0, 2, 0]
]
```
Output: `-1`
Explanation: Every column is blocked by forbidden cells, so no top-to-bottom path can be formed.
## Input / Output
- Input: `runes`, a 2D integer array of size `rows x cols` with values in `{0, 1, 2}`.
- Output: an integer — the minimum number of empty cells to charge, or `-1` if no top-to-bottom path is possible.
## Constraints
- `1 <= rows, cols <= 1000`.
- `rows * cols <= 10^6`.
- Each cell of `runes` is `0`, `1`, or `2`.
- Traversal and adjacency are restricted to the four cardinal directions; diagonal moves are not allowed.
- When `rows == 1`, the top edge and bottom edge are the same row: the spell is castable (answer `0`) as long as that single row contains at least one charged cell, and otherwise charging any one non-forbidden cell in that row suffices.
Quick Answer: This question evaluates proficiency in graph traversal and shortest-path optimization within a 2D grid, testing the ability to find minimum-cost connectivity under constraints. It assesses practical application of BFS-based algorithms, including 0-1 BFS or Dijkstra's variant, commonly used to gauge depth of knowledge in graph theory and matrix traversal at a hard difficulty level.
You are given a magic grid `runes` with `rows` rows and `cols` columns. Each cell is one of three values:
- `0` — an empty cell.
- `1` — a charged rune already placed in the cell.
- `2` — a forbidden cell. A forbidden cell can never hold a rune and can never be traversed.
A spell is **castable** when magic can flow continuously from the **top edge** (row `0`) to the **bottom edge** (row `rows - 1`) through charged runes. Magic flows between two cells only if both are charged (value `1`) and are directly adjacent in one of the **four cardinal directions** (up, down, left, right — never diagonally). The spell is castable if there exists a path of 4-directionally adjacent charged cells that starts in row `0` and ends in row `rows - 1`.
You may **charge** additional empty cells (turn a `0` into a `1`) at a cost of `1` rune each. You may not change forbidden cells (`2`) and you may not place a rune on a forbidden cell.
Return the **minimum number of empty cells you must charge** so that the spell becomes castable, or `-1` if it is impossible (every candidate route is blocked by forbidden cells). If the grid is already castable, return `0`.
**Note:** When `rows == 1`, the top and bottom edge are the same row — the answer is `0` if that row already has a charged cell, otherwise `1` (charge any non-forbidden cell), or `-1` if the entire row is forbidden.
Constraints
- 1 <= rows, cols <= 1000
- rows * cols <= 10^6
- Each cell of runes is 0, 1, or 2
- Traversal and adjacency are restricted to the four cardinal directions; diagonal moves are not allowed
Examples
Input: ([[1, 0, 0], [0, 0, 0], [0, 0, 1]],)
Expected Output: 2
Explanation: Charge (1,0) and (2,0) to form the path (0,0)->(1,0)->(2,0) from the top row to the bottom row. Only 2 empty cells are needed.
Input: ([[1, 1, 1], [2, 2, 1], [1, 1, 1]],)
Expected Output: 0
Explanation: A charged path already exists, e.g. (0,2)->(1,2)->(2,2), so no new runes are required.
Input: ([[0, 2, 0], [2, 2, 2], [0, 2, 0]],)
Expected Output: -1
Explanation: The middle row is entirely forbidden, so no column can carry a path from the top edge to the bottom edge.
Input: ([[1]],)
Expected Output: 0
Explanation: Single-cell grid that is already charged; top and bottom edge coincide, so the answer is 0.
Input: ([[0]],)
Expected Output: 1
Explanation: Single empty cell; charging it for cost 1 makes the (one-row) spell castable.
Input: ([[2]],)
Expected Output: -1
Explanation: The only cell is forbidden, so no rune can ever be placed and no path exists.
Input: ([[0, 0, 0], [0, 0, 0], [0, 0, 0]],)
Expected Output: 3
Explanation: All cells empty; a straight 3-cell column (one cell per row) is the cheapest path, costing 3 charges.
Input: ([[1, 2], [2, 1]],)
Expected Output: -1
Explanation: The two charged cells are only diagonally adjacent and the other two cells are forbidden, so no 4-directional path links the top row to the bottom row.
Input: ([[1, 0], [1, 0], [0, 1]],)
Expected Output: 1
Explanation: The path (0,0)->(1,0)->(2,0) uses two charged cells and one empty cell (2,0), reaching the bottom row for a cost of 1.
Input: ([[0, 1, 0], [2, 1, 2], [0, 1, 0]],)
Expected Output: 0
Explanation: The middle column is fully charged: (0,1)->(1,1)->(2,1) connects top to bottom with no new charges.
Hints
- Model this as a shortest-path problem on a grid where the 'distance' of a path is the number of empty (0) cells it passes through. Entering a charged cell (1) costs 0, entering an empty cell (0) costs 1, and forbidden cells (2) are walls.
- Because every edge weight is either 0 or 1, you can use 0-1 BFS with a deque: push 0-cost moves to the front and 1-cost moves to the back. This runs in O(rows*cols) instead of O(E log V) with a heap.
- Seed the deque with every non-forbidden cell in row 0 (each with cost equal to its own entry cost), then relax outward. The answer is the minimum distance reached at any cell in the bottom row, or -1 if none is reachable.