3552. Grid Teleportation Traversal
Problem Description
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 i
th row and j
th 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
.
Intuition
The problem asks for the minimum number of moves to reach the bottom-right cell on a grid with obstacles and special portal cells. Normally, we can explore the grid using Breadth-First Search (BFS), as it gives the shortest path in an unweighted grid. However, the portals add a twist: stepping on a portal lets you instantly travel to any other matching portal cell, but only once per portal letter.
To find the shortest path, treat a normal move to an empty cell as costing one move, and using a portal as costing zero moves since it's instantaneous. This fits the "0-1 BFS" model, where we use a double-ended queue to prioritize zero-cost moves (portals) over regular moves (adjacent steps). By tracking which portals have already been used, and always exploring all possible zero-cost (teleportation) moves before regular ones, we ensure we never miss a quicker path using portals. This idea leads us to an efficient way to compute the answer.
Solution Approach
This solution uses a 0-1 BFS (Breadth-First Search) strategy because the problem consists of two types of moves: adjacent cell moves that cost 1 step and instant portal jumps that cost 0 steps.
Key steps:
-
Portal Mapping: First, for each portal letter (
'A'
-'Z'
) found in the grid, record all its coordinates in a dictionary. This allows instant lookup of all other positions for teleportation when stepping on a portal cell. -
Distance Matrix: Maintain a 2D
dist
array representing the minimum number of moves to reach each cell. Initialize every cell with infinity (inf
) except the starting cell at(0, 0)
, which is set to 0. -
0-1 BFS with Deque: Use a double-ended queue (
deque
) to perform BFS. This allows cells reached via a portal (cost 0) to be prioritized and processed earlier than regular moves (cost 1). -
Move and Teleportation Logic: At each BFS step:
- If on a portal cell (say letter
'A'
) and haven't used this portal yet, push all other cells with the same portal letter to the front of the queue, and set their distance equal to the current cell. - For normal adjacent cells, push them to the back of the queue with an incremented distance (
+1
).
- If on a portal cell (say letter
-
Portal Use Tracking: Once a portal letter is used, remove it from the portal mapping. This ensures each portal is only used once, as required by the problem.
-
Termination: If the destination
(m-1, n-1)
is reached, return the associated distance. If the queue empties without reaching it, return-1
to indicate that it's impossible.
Summary: Using 0-1 BFS allows us to efficiently handle both move types and always find the shortest path. By managing portals as 0-cost transitions and ensuring once-only use per letter, the algorithm stays correct and efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small grid for illustration:
matrix = [ ".A.", "#B#", ".A." ]
.
: empty cell#
: obstacleA
andB
: portal cells
Step-by-step 0-1 BFS Approach:
-
Portal Mapping
- 'A' is at (0,1) and (2,1)
- 'B' is at (1,1)
-
Initialization
dist[0][0]=0
(start at top-left)- All other distances set to infinity.
- Deque starts with
(0,0)
- Unused portals: 'A', 'B'
-
First BFS Loop
- Current cell: (0,0),
dist=0
. - Check neighbors: (0,1) is 'A'. Move to (0,1):
dist=1
, enqueue to back. (1,0) is '#': obstacle, skip it.
- Current cell: (0,0),
-
Next BFS Loop
- Current cell: (0,1),
dist=1
- 'A' portal and unused. Teleport to (2,1) for free: enqueue (2,1) to front with
dist=1
. - Mark 'A' as used.
- Check neighbors: (0,0) [already visited], (0,2) [empty], (1,1) is 'B'. Enqueue (0,2) and (1,1), both with
dist=2
.
- Current cell: (0,1),
-
Next BFS Step: Portal Use
- (2,1) dequeued from front,
dist=1
. - Neighbors: (1,1) is 'B' (already in queue), (2,0) and (2,2) are empty. Enqueue (2,0), (2,2) with
dist=2
.
- (2,1) dequeued from front,
-
Continue BFS
- (0,2) dequeued next. Neighbors are either obstacle or already visited.
- (1,1) dequeued. This is portal 'B', but there are no other 'B' cells, so no teleportation happens.
-
Last steps
- (2,0) and (2,2) dequeued.
- (2,2) is the bottom-right cell: reached at
dist=2
.
Result: The minimum number of moves is 2:
- (0,0) β (0,1) [A] β teleport to (2,1) β (2,2)
This example illustrates how the 0-1 BFS explores zero-cost portal jumps before costlier steps, maps portal letters, and ensures each teleportation is only used once.
Solution Implementation
1from typing import List
2from collections import defaultdict, deque
3from math import inf
4
5class Solution:
6 def minMoves(self, matrix: List[str]) -> int:
7 rows, cols = len(matrix), len(matrix[0])
8
9 # Record all positions for each alphabetic teleport cell.
10 teleport = defaultdict(list)
11 for i, row in enumerate(matrix):
12 for j, char in enumerate(row):
13 if char.isalpha():
14 teleport[char].append((i, j))
15
16 # Possible movement directions: up, right, down, left
17 directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
18
19 # Distance matrix, initialized to infinity
20 dist = [[inf] * cols for _ in range(rows)]
21 dist[0][0] = 0
22
23 # BFS queue, starting from the top-left cell
24 queue = deque([(0, 0)])
25
26 while queue:
27 x, y = queue.popleft()
28 current_dist = dist[x][y]
29
30 # If destination (bottom-right) is reached, return the distance
31 if x == rows - 1 and y == cols - 1:
32 return current_dist
33
34 cell_value = matrix[x][y]
35
36 # Teleportation: If current cell is teleport and not already used
37 if cell_value in teleport:
38 for tx, ty in teleport[cell_value]:
39 if current_dist < dist[tx][ty]:
40 dist[tx][ty] = current_dist
41 queue.appendleft((tx, ty)) # Prioritize teleportation (0-cost)
42 # Remove from teleport map to prevent re-use
43 del teleport[cell_value]
44
45 # Move to adjacent cells (cost +1)
46 for dx, dy in directions:
47 nx, ny = x + dx, y + dy
48 # Check boundaries and obstacles
49 if (
50 0 <= nx < rows
51 and 0 <= ny < cols
52 and matrix[nx][ny] != '#'
53 and current_dist + 1 < dist[nx][ny]
54 ):
55 dist[nx][ny] = current_dist + 1
56 queue.append((nx, ny))
57
58 # If goal is unreachable, return -1
59 return -1
60
1class Solution {
2 public int minMoves(String[] matrix) {
3 int m = matrix.length;
4 int n = matrix[0].length();
5
6 // Build mapping: character -> list of its coordinates in the matrix
7 Map<Character, List<int[]>> teleports = new HashMap<>();
8 for (int row = 0; row < m; row++) {
9 for (int col = 0; col < n; col++) {
10 char ch = matrix[row].charAt(col);
11 if (Character.isAlphabetic(ch)) {
12 teleports.computeIfAbsent(ch, k -> new ArrayList<>())
13 .add(new int[]{row, col});
14 }
15 }
16 }
17
18 // Directions: up, right, down, left
19 int[] dirs = {-1, 0, 1, 0, -1};
20 int INF = Integer.MAX_VALUE / 2;
21 int[][] distance = new int[m][n];
22 for (int[] arr : distance) Arrays.fill(arr, INF);
23
24 // BFS initialization
25 distance[0][0] = 0;
26 Deque<int[]> queue = new ArrayDeque<>();
27 queue.add(new int[]{0, 0});
28
29 while (!queue.isEmpty()) {
30 int[] curr = queue.pollFirst();
31 int currRow = curr[0];
32 int currCol = curr[1];
33 int currDist = distance[currRow][currCol];
34
35 // If destination reached, return answer
36 if (currRow == m - 1 && currCol == n - 1) return currDist;
37
38 char currChar = matrix[currRow].charAt(currCol);
39
40 // Teleport to all other cells with the same alphabet character
41 if (teleports.containsKey(currChar)) {
42 for (int[] pos : teleports.get(currChar)) {
43 int tr = pos[0], tc = pos[1];
44 if (currDist < distance[tr][tc]) {
45 distance[tr][tc] = currDist; // teleportation doesn't increase step
46 queue.addFirst(new int[]{tr, tc});
47 }
48 }
49 teleports.remove(currChar); // Use teleportation only once per character
50 }
51
52 // Explore four directions
53 for (int d = 0; d < 4; d++) {
54 int nextRow = currRow + dirs[d];
55 int nextCol = currCol + dirs[d + 1];
56
57 // Check bounds and if not a wall ('#')
58 if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n &&
59 matrix[nextRow].charAt(nextCol) != '#') {
60 if (currDist + 1 < distance[nextRow][nextCol]) {
61 distance[nextRow][nextCol] = currDist + 1;
62 queue.addLast(new int[]{nextRow, nextCol});
63 }
64 }
65 }
66 }
67 // No valid path to destination
68 return -1;
69 }
70}
71
1class Solution {
2public:
3 int minMoves(vector<string>& matrix) {
4 // Grid dimensions
5 int rows = matrix.size(), cols = matrix[0].size();
6
7 // Map from character to all its positions (used for teleportation)
8 unordered_map<char, vector<pair<int, int>>> teleport;
9 for (int i = 0; i < rows; ++i)
10 for (int j = 0; j < cols; ++j) {
11 char cell = matrix[i][j];
12 // Only consider alphabetic characters as teleporters
13 if (isalpha(cell))
14 teleport[cell].emplace_back(i, j);
15 }
16
17 // Directions for moving: up, right, down, left
18 int dr[5] = {-1, 0, 1, 0, -1};
19
20 // Initialize distances to infinity
21 int INF = numeric_limits<int>::max() / 2;
22 vector<vector<int>> dist(rows, vector<int>(cols, INF));
23 dist[0][0] = 0; // Start cell
24
25 // 0-1 BFS deque
26 deque<pair<int, int>> dq;
27 dq.emplace_back(0, 0);
28
29 while (!dq.empty()) {
30 auto [r, c] = dq.front();
31 dq.pop_front();
32 int d = dist[r][c];
33
34 // If reached the target cell, return the number of moves
35 if (r == rows - 1 && c == cols - 1)
36 return d;
37
38 // Teleportation: from current cell to all cells with same teleporter character
39 char cell = matrix[r][c];
40 if (teleport.count(cell)) {
41 for (auto [tr, tc] : teleport[cell]) {
42 if (d < dist[tr][tc]) {
43 dist[tr][tc] = d; // Teleport (zero cost)
44 dq.emplace_front(tr, tc);
45 }
46 }
47 teleport.erase(cell); // Process each teleporter just once
48 }
49
50 // Adjacent moves (cost 1)
51 for (int idx = 0; idx < 4; ++idx) {
52 int nr = r + dr[idx], nc = c + dr[idx + 1];
53 // Check boundaries and wall cells
54 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] != '#') {
55 if (d + 1 < dist[nr][nc]) {
56 dist[nr][nc] = d + 1;
57 dq.emplace_back(nr, nc);
58 }
59 }
60 }
61 }
62
63 // No possible way to reach target
64 return -1;
65 }
66};
67
1// Directions for moving up, right, down, left on the grid
2const directions = [-1, 0, 1, 0, -1];
3
4// Infinity value for unreachable cells
5const INF = Number.MAX_SAFE_INTEGER;
6
7/**
8 * Calculates the minimum number of moves needed to go from the top-left
9 * to the bottom-right cell in the matrix, considering teleportation by matching letters.
10 * @param matrix - Array of strings representing the grid
11 * @returns Minimum moves required, or -1 if unreachable
12 */
13function minMoves(matrix: string[]): number {
14 const rows = matrix.length;
15 const cols = matrix[0].length;
16
17 // Mapping each letter to all its positions on the grid
18 const teleports = new Map<string, [number, number][]>();
19 for (let i = 0; i < rows; i++) {
20 for (let j = 0; j < cols; j++) {
21 const char = matrix[i][j];
22 if (/^[A-Za-z]$/.test(char)) {
23 if (!teleports.has(char)) teleports.set(char, []);
24 teleports.get(char)!.push([i, j]);
25 }
26 }
27 }
28
29 // Distance matrix; fill with INF by default
30 const distance: number[][] = Array.from({ length: rows }, () => Array<number>(cols).fill(INF));
31 distance[0][0] = 0;
32
33 // Manual double-ended queue for 0-1 BFS
34 const queueCapacity = rows * cols * 2 + 5;
35 const deque = new Array<[number, number]>(queueCapacity);
36 let left = queueCapacity >> 1, right = queueCapacity >> 1;
37
38 // Queue operations
39 const pushFront = (val: [number, number]) => { deque[--left] = val; };
40 const pushBack = (val: [number, number]) => { deque[right++] = val; };
41 const popFront = (): [number, number] => deque[left++];
42 const isEmpty = () => left === right;
43
44 // Start from the top-left cell
45 pushBack([0, 0]);
46
47 // 0-1 BFS loop
48 while (!isEmpty()) {
49 const [curRow, curCol] = popFront();
50 const curDist = distance[curRow][curCol];
51
52 // If destination reached, return the answer
53 if (curRow === rows - 1 && curCol === cols - 1) return curDist;
54
55 const curChar = matrix[curRow][curCol];
56
57 // Teleport using the current letter (if any unvisited remain)
58 if (teleports.has(curChar)) {
59 for (const [nextRow, nextCol] of teleports.get(curChar)!) {
60 if (curDist < distance[nextRow][nextCol]) {
61 distance[nextRow][nextCol] = curDist; // Teleportation, no extra cost
62 pushFront([nextRow, nextCol]);
63 }
64 }
65 // Delete to avoid revisiting teleports of this letter
66 teleports.delete(curChar);
67 }
68
69 // Standard grid moves (up, right, down, left)
70 for (let d = 0; d < 4; d++) {
71 const newRow = curRow + directions[d];
72 const newCol = curCol + directions[d + 1];
73 // Check bounds and obstacles
74 if (
75 newRow >= 0 && newRow < rows &&
76 newCol >= 0 && newCol < cols &&
77 matrix[newRow][newCol] !== '#' &&
78 curDist + 1 < distance[newRow][newCol]
79 ) {
80 distance[newRow][newCol] = curDist + 1;
81 pushBack([newRow, newCol]);
82 }
83 }
84 }
85
86 // If the bottom-right cell is unreachable
87 return -1;
88}
89
Time and Space Complexity
-
Time Complexity:
O(m * n)
The BFS traverses each cell at most once. Each teleport operation (using matching characters) is also processed once per character due to deletion fromg
. Therefore, the total operations are bounded by the number of cells (m * n
). -
Space Complexity:
O(m * n)
Thedist
array and the queueq
each take up toO(m * n)
space. The dictionaryg
also stores at mostO(m * n)
positions corresponding to matching cells, leading the overall space to beO(m * n)
.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Donβt Miss This!