Watch 5 video solutions for Grid Teleportation Traversal, a medium level problem involving Array, Hash Table, Breadth-First Search. This walkthrough by Leet's Code has 741 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D character grid matrix of size m x n, represented as an array of strings, where matrix[i][j] represents the cell at the intersection of the ith row and jth column. Each cell is one of the following:
'.' representing an empty cell.'#' representing an obstacle.'A'-'Z') representing a teleportation portal.You start at the top-left cell (0, 0), and your goal is to reach the bottom-right cell (m - 1, n - 1). You can move from the current cell to any adjacent cell (up, down, left, right) as long as the destination cell is within the grid bounds and is not an obstacle.
If you step on a cell containing a portal letter and you haven't used that portal letter before, you may instantly teleport to any other cell in the grid with the same letter. This teleportation does not count as a move, but each portal letter can be used at most once during your journey.
Return the minimum number of moves required to reach the bottom-right cell. If it is not possible to reach the destination, return -1.
Example 1:
Input: matrix = ["A..",".A.","..."]
Output: 2
Explanation:
(0, 0) to (1, 1).(1, 1) to (1, 2).(1, 2) to (2, 2).Example 2:
Input: matrix = [".#...",".#.#.",".#.#.","...#."]
Output: 13
Explanation:
Constraints:
1 <= m == matrix.length <= 1031 <= n == matrix[i].length <= 103matrix[i][j] is either '#', '.', or an uppercase English letter.matrix[0][0] is not an obstacle.Problem Overview: Grid Teleportation Traversal asks you to move from the start of a matrix to a target cell while handling special teleport tiles. Normal moves go to adjacent cells, but matching teleport markers allow instant jumps between multiple grid positions. The goal is to compute the minimum number of steps required to reach the destination.
Approach 1: BFS with Teleport Mapping (O(m*n + k), Space O(m*n))
The straightforward solution models the grid as a graph and runs Breadth-First Search. Each cell is a node, and edges connect the four adjacent positions in the matrix. Before traversal, iterate through the grid and build a hash table that maps each teleport symbol to a list of coordinates where it appears. During BFS, when you step on a teleport cell, you enqueue all other coordinates with the same symbol.
The key idea is that teleportation acts like additional edges in the graph. BFS guarantees the shortest path in an unweighted grid. However, repeatedly expanding the same teleport list can cause redundant work if the same letter appears many times. In worst cases, each visit may scan the same teleport group again, increasing overhead.
Approach 2: 0-1 BFS with Teleport Optimization (O(m*n), Space O(m*n))
The optimized method treats teleport moves as zero-cost edges and normal grid moves as cost-one edges. This fits the classic 0-1 BFS pattern using a deque. Adjacent moves push to the back of the deque (cost 1), while teleport jumps push to the front (cost 0). The algorithm maintains a distance matrix and processes states in increasing cost order.
To avoid repeated teleport expansions, store all teleport coordinates in a hash map and remove or mark a teleport group after it is used once. This ensures each teleport set is processed only a single time. The deque-based traversal keeps the algorithm linear relative to the number of grid cells.
The main insight is that teleport edges should not increase the path length. By modeling them as zero-cost transitions and preventing repeated expansions, the traversal behaves like a shortest-path search on a sparse graph. This makes the runtime effectively proportional to the grid size.
Recommended for interviews: Start by explaining the graph modeling and standard BFS approach to show baseline understanding. Then move to the 0-1 BFS optimization, which interviewers typically expect for problems mixing zero-cost and unit-cost transitions. Demonstrating how to store teleport positions in a hash map and process each group once shows strong control over graph traversal patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Teleport Mapping | O(m*n + k) | O(m*n) | Good baseline approach when teleport groups are small and repeated scans are inexpensive. |
| 0-1 BFS (Optimal) | O(m*n) | O(m*n) | Best for large grids with many teleport cells where zero-cost transitions must be processed efficiently. |