Grid Teleportation Traversal solution and explanation
4 more videos on this problem
LeetCode 3552. Grid Teleportation Traversal | DFS | BFS | Priority Queue | Graph | MediumLeet's Code · 26:51 · 796 views
Grid Teleportation Traversal (Leetcode Weekly 450)Soumya Bhattacharjee · 13:03 · 743 views
3552. Grid Teleportation Traversal (Leetcode Medium)Programming Live with Larry · 16:30 · 609 views
Leetcode 3552. Grid Teleportation Traversal | Weekly Contest 450 | Java Solution || BFSExpertFunda · 16:38 · 394 views
Weekly Contest 450 LeetCode-C 3552 Grid Teleportation Traversal Using Dijkstra/BFSDesiCoding · 25:35 · 95 views
The problem
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.- An uppercase letter (
'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:
- Before the first move, teleport from
(0, 0)to(1, 1). - In the first move, move from
(1, 1)to(1, 2). - In the second move, move from
(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.
Approach overview
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.
Solution
We can use 0-1 BFS to solve this problem. We start from the top-left cell and use a double-ended queue to store the coordinates of the current cell. Each time we dequeue a cell, we check its four adjacent cells. If an adjacent cell is an empty cell and has not been visited, we add it to the queue and update its distance.
If an adjacent cell is a portal, we add it to the front of the queue and update its distance. We also need to maintain a dictionary to store the positions of each portal so that we can quickly find them when using a portal.
We also need a 2D array to store the distance for each cell, initialized to infinity. We set the distance of the starting point to 0 and then start BFS.
During the BFS process, we check whether each cell is the destination. If it is, we return its distance. If the queue is empty and the destination has not been reached, we return -1.
The time complexity is O(m times n), and the space complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.
class Solution:
def minMoves(self, matrix: List[str]) -> int:
m, n = len(matrix), len(matrix[0])
g = defaultdict(list)
for i, row in enumerate(matrix):
for j, c in enumerate(row):
if c.isalpha():
g[c].append((i, j))
dirs = (-1, 0, 1, 0, -1)
dist = [[inf] * n for _ in range(m)]
dist[0][0] = 0
q = deque([(0, 0)])
while q:
i, j = q.popleft()
d = dist[i][j]
if i == m - 1 and j == n - 1:
return d
c = matrix[i][j]
if c in g:
for x, y in g[c]:
if d < dist[x][y]:
dist[x][y] = d
q.appendleft((x, y))
del g[c]
for a, b in pairwise(dirs):
x, y = i + a, j + b
if (
0 <= x < m
and 0 <= y < n
and matrix[x][y] != "#"
and d + 1 < dist[x][y]
):
dist[x][y] = d + 1
q.append((x, y))
return -1class Solution {
public int minMoves(String[] matrix) {
int m = matrix.length, n = matrix[0].length();
Map<Character, List<int[]>> g = new HashMap<>();
for (int i = 0; i < m; i++) {
String row = matrix[i];
for (int j = 0; j < n; j++) {
char c = row.charAt(j);
if (Character.isAlphabetic(c)) {
g.computeIfAbsent(c, k -> new ArrayList<>()).add(new int[] {i, j});
}
}
}
int[] dirs = {-1, 0, 1, 0, -1};
int INF = Integer.MAX_VALUE / 2;
int[][] dist = new int[m][n];
for (int[] arr : dist) Arrays.fill(arr, INF);
dist[0][0] = 0;
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[] {0, 0});
while (!q.isEmpty()) {
int[] cur = q.pollFirst();
int i = cur[0], j = cur[1];
int d = dist[i][j];
if (i == m - 1 && j == n - 1) return d;
char c = matrix[i].charAt(j);
if (g.containsKey(c)) {
for (int[] pos : g.get(c)) {
int x = pos[0], y = pos[1];
if (d < dist[x][y]) {
dist[x][y] = d;
q.addFirst(new int[] {x, y});
}
}
g.remove(c);
}
for (int idx = 0; idx < 4; idx++) {
int a = dirs[idx], b = dirs[idx + 1];
int x = i + a, y = j + b;
if (0 <= x && x < m && 0 <= y && y < n && matrix[x].charAt(y) != '#'
&& d + 1 < dist[x][y]) {
dist[x][y] = d + 1;
q.addLast(new int[] {x, y});
}
}
}
return -1;
}
}class Solution {
public:
int minMoves(vector<string>& matrix) {
int m = matrix.size(), n = matrix[0].size();
unordered_map<char, vector<pair<int, int>>> g;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) {
char c = matrix[i][j];
if (isalpha(c)) g[c].push_back({i, j});
}
int dirs[5] = {-1, 0, 1, 0, -1};
int INF = numeric_limits<int>::max() / 2;
vector<vector<int>> dist(m, vector<int>(n, INF));
dist[0][0] = 0;
deque<pair<int, int>> q;
q.push_back({0, 0});
while (!q.empty()) {
auto [i, j] = q.front();
q.pop_front();
int d = dist[i][j];
if (i == m - 1 && j == n - 1) return d;
char c = matrix[i][j];
if (g.count(c)) {
for (auto [x, y] : g[c])
if (d < dist[x][y]) {
dist[x][y] = d;
q.push_front({x, y});
}
g.erase(c);
}
for (int idx = 0; idx < 4; ++idx) {
int x = i + dirs[idx], y = j + dirs[idx + 1];
if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] != '#' && d + 1 < dist[x][y]) {
dist[x][y] = d + 1;
q.push_back({x, y});
}
}
}
return -1;
}
};function minMoves(matrix: string[]): number {
const m = matrix.length,
n = matrix[0].length;
const g = new Map<string, [number, number][]>();
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const c = matrix[i][j];
if (/^[A-Za-z]$/.test(c)) {
if (!g.has(c)) g.set(c, []);
g.get(c)!.push([i, j]);
}
}
}
const dirs = [-1, 0, 1, 0, -1];
const INF = Number.MAX_SAFE_INTEGER;
const dist: number[][] = Array.from({ length: m }, () => Array(n).fill(INF));
dist[0][0] = 0;
const cap = m * n * 2 + 5;
const dq = new Array<[number, number]>(cap);
let l = cap >> 1,
r = cap >> 1;
const pushFront = (v: [number, number]) => {
dq[--l] = v;
};
const pushBack = (v: [number, number]) => {
dq[r++] = v;
};
const popFront = (): [number, number] => dq[l++];
const empty = () => l === r;
pushBack([0, 0]);
while (!empty()) {
const [i, j] = popFront();
const d = dist[i][j];
if (i === m - 1 && j === n - 1) return d;
const c = matrix[i][j];
if (g.has(c)) {
for (const [x, y] of g.get(c)!) {
if (d < dist[x][y]) {
dist[x][y] = d;
pushFront([x, y]);
}
}
g.delete(c);
}
for (let idx = 0; idx < 4; idx++) {
const x = i + dirs[idx],
y = j + dirs[idx + 1];
if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] !== '#' && d + 1 < dist[x][y]) {
dist[x][y] = d + 1;
pushBack([x, y]);
}
}
}
return -1;
}type pair struct{ x, y int }
func minMoves(matrix []string) int {
m, n := len(matrix), len(matrix[0])
g := make(map[rune][]pair)
for i := 0; i < m; i++ {
for j, c := range matrix[i] {
if unicode.IsLetter(c) {
g[c] = append(g[c], pair{i, j})
}
}
}
dirs := []int{-1, 0, 1, 0, -1}
INF := 1 << 30
dist := make([][]int, m)
for i := range dist {
dist[i] = make([]int, n)
for j := range dist[i] {
dist[i][j] = INF
}
}
dist[0][0] = 0
q := list.New()
q.PushBack(pair{0, 0})
for q.Len() > 0 {
cur := q.Remove(q.Front()).(pair)
i, j := cur.x, cur.y
d := dist[i][j]
if i == m-1 && j == n-1 {
return d
}
c := rune(matrix[i][j])
if v, ok := g[c]; ok {
for _, p := range v {
x, y := p.x, p.y
if d < dist[x][y] {
dist[x][y] = d
q.PushFront(pair{x, y})
}
}
delete(g, c)
}
for idx := 0; idx < 4; idx++ {
x, y := i+dirs[idx], j+dirs[idx+1]
if 0 <= x && x < m && 0 <= y && y < n && matrix[x][y] != '#' && d+1 < dist[x][y] {
dist[x][y] = d + 1
q.PushBack(pair{x, y})
}
}
}
return -1
}Complexity analysis
| 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. |
Frequently asked questions
Is Grid Teleportation Traversal easy or hard?
Grid Teleportation Traversal is generally classified as a Medium problem. The BFS modeling is straightforward, but recognizing that teleport edges have zero cost and applying 0-1 BFS is the key step that raises the difficulty.
Grid Teleportation Traversal Python/Java solution
Most implementations follow the same structure across languages: preprocess teleport cells into a hash map, maintain a deque for 0-1 BFS, and track distances in a matrix. Python typically uses collections.deque, while Java uses ArrayDeque. C++, Go, and TypeScript implementations follow the same traversal logic.
How to solve Grid Teleportation Traversal in O(n)?
Model the grid as a graph and apply 0-1 BFS. Use a deque where normal moves push to the back and teleport moves push to the front. Maintain a hash map from teleport symbols to their coordinates and remove a group after processing to prevent repeated expansions. This keeps traversal linear relative to the grid size.
What is the best approach for Grid Teleportation Traversal?
The most efficient solution uses a 0-1 BFS traversal. Adjacent grid moves are treated as cost 1 while teleport jumps are cost 0. A deque processes nodes in increasing distance order, and teleport groups are stored in a hash map so each group is expanded only once. This achieves O(m*n) time complexity.
Is Grid Teleportation Traversal asked at Google/Amazon/Meta?
Grid traversal and teleport-style problems are common variations of graph shortest-path questions asked by companies like Google, Amazon, and Meta. Interviewers use them to test BFS, graph modeling, and optimization techniques such as 0-1 BFS or multi-source traversal.
What data structure is used in Grid Teleportation Traversal?
Key data structures include a queue or deque for BFS traversal, a hash table mapping teleport symbols to grid coordinates, and a visited or distance matrix. The deque is especially important for implementing the 0-1 BFS optimization.
What is the time complexity of Grid Teleportation Traversal?
The optimal 0-1 BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is processed once and each teleport group is expanded once. Space complexity is also O(m*n) for the visited or distance matrix and teleport index.