LeetCode Problem 3552

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Breadth-First Search, Matrix

Solution

Problem Understanding

This problem presents a 2D grid traversal scenario with obstacles and teleportation portals. You are given a matrix of characters representing cells. Empty cells '.' are freely passable, '#' represents obstacles that block movement, and uppercase letters 'A'-'Z' are teleportation portals. The task is to move from the top-left (0, 0) to the bottom-right (m-1, n-1) in the minimum number of moves. You can move orthogonally (up, down, left, right), and stepping onto a portal allows instant teleportation to any other cell with the same letter, but each portal letter can only be used once. The teleportation itself does not count as a move.

The constraints indicate that the grid can be very large (m, n <= 10^3), so brute-force approaches that explore all paths are infeasible. Each cell is guaranteed to be either an obstacle, empty, or a portal, and the starting cell is always free. Important edge cases include grids with no path to the target, grids where portals are critical to reach the destination, and grids where teleportation may or may not save moves.

The problem requires careful handling of BFS traversal while incorporating teleportation rules efficiently.

Approaches

The brute-force approach would attempt to enumerate all possible paths from start to end, considering teleportation options at each step. While this would eventually yield the correct answer, it is computationally prohibitive because the number of paths grows exponentially with grid size, making it impractical for large grids up to 10^6 cells.

The optimal approach leverages Breadth-First Search (BFS) for shortest-path exploration. BFS is ideal because it naturally explores all positions in increasing order of distance from the start, guaranteeing that the first time the target is reached is the minimum number of moves. To handle portals, we maintain a mapping of letters to their positions and a set of used portals. When we step onto a portal for the first time, we enqueue all other cells with the same letter for exploration at no extra move cost. BFS ensures minimal moves while a visited set prevents redundant work.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^(m*n))	O(m*n)	Explore all paths including teleportations recursively, impractical for large grids
Optimal	O(m*n + P)	O(m*n + P)	BFS with teleportation, where P is the total number of portal cells

Algorithm Walkthrough

1. Preprocess the grid to create a hash map (portals) from portal letters to the list of all coordinates containing that letter. This allows O(1) access to teleportation targets.
2. Initialize a BFS queue starting at (0, 0) with a distance of 0 moves. Maintain a visited set to track cells already explored.
3. Create a used_portals set to track which portal letters have already been used.
4. While the queue is not empty, dequeue the current cell (x, y) and its distance.
5. If (x, y) is the target (m-1, n-1), return the distance because BFS guarantees it is the minimum.
6. Explore all four orthogonal neighbors. If a neighbor is within bounds, not an obstacle, and not yet visited, mark it visited and enqueue it with distance incremented by 1.
7. If the current cell contains a portal letter and the letter has not been used, mark the portal as used. Enqueue all other cells with the same portal letter at the same distance (teleportation is free), and mark them visited.
8. If BFS finishes without reaching the target, return -1 indicating no path exists.

This works because BFS inherently guarantees that each cell is first reached in the minimum number of moves. Teleportation is handled carefully to avoid revisiting and infinite loops. The problem asks us to find the minimum number of moves required to travel from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) in a 2D grid. Each cell is either empty ('.'), blocked ('#'), or contains an uppercase letter representing a teleportation portal.

Movement is allowed in the four cardinal directions, and each such move costs exactly one step. In addition to normal movement, there is a special teleportation rule: if you land on a portal letter for the first time, you are allowed to instantly teleport to any other cell containing the same letter. This teleportation does not consume a move, but each distinct letter can only trigger teleportation once during the entire traversal.

The key goal is to compute the shortest path under a mixed-weight system: normal moves cost 1, teleportation edges cost 0 but are constrained to a single activation per letter.

The constraints indicate a grid size up to 1,000 by 1,000, meaning up to 1,000,000 cells. This makes any algorithm worse than linear or near-linear in grid size infeasible. A naive approach that recomputes paths or explores teleportation repeatedly would be too slow.

Important edge cases include grids with no portals at all, grids where the start or end is isolated by obstacles, grids where teleportation provides a large shortcut, and grids where multiple letters exist but are never beneficial to use. We are guaranteed that (0, 0) is not an obstacle, but the destination may still be unreachable.

Approaches

Brute Force Approach

A brute force solution would attempt to treat each teleport activation as a branching decision in a shortest path search. From each cell, we would explore all possible moves and, upon encountering a portal, recursively attempt teleportation to every other same-letter cell while tracking whether that letter has already been used.

This leads to an exponential explosion in states because each portal letter introduces a binary decision (used or not used), and revisiting states across different paths becomes extremely expensive. Even with memoization, the state space becomes large due to combinations of grid position and used portal set.

Optimal Approach Insight

The correct observation is that this is a shortest path problem on a graph with two types of weighted edges: normal moves with cost 1 and teleportation edges with cost 0. This naturally maps to a shortest path algorithm on weighted graphs, specifically a 0-1 BFS or Dijkstra’s algorithm.

However, we must also enforce that each letter’s teleportation is used at most once. This can be handled by maintaining a boolean set indicating whether a letter’s teleportation has already been expanded. When we first process any cell of a given letter, we expand all its teleport destinations exactly once.

This ensures that teleportation behaves like a one-time zero-cost "super edge expansion" without duplicating work.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all teleport usage combinations
Optimal (0-1 BFS + portal expansion)	O(mn)	O(mn)	Each cell and portal processed at most once

Algorithm Walkthrough

The optimal solution uses a 0-1 BFS strategy with a deque to handle mixed edge weights efficiently.

Step-by-step process

1. Preprocess the grid to build a mapping from each portal letter to a list of all its coordinates. This allows instant access to all teleport destinations for a letter.
2. Initialize a distance matrix dist of size m x n, filled with infinity. This tracks the minimum number of moves required to reach each cell.
3. Use a deque to perform 0-1 BFS starting from (0, 0). Set dist[0][0] = 0 and push it into the deque.
4. Maintain a set used_portal to track which portal letters have already triggered teleportation expansion.
5. While the deque is not empty, pop a cell (r, c) and consider its current distance d.
6. Explore the four adjacent neighbors. If moving to a neighbor costs 1 step and improves its known distance, update dist and push it to the back of the deque.
7. If the current cell contains a portal letter that has not yet been used, expand teleportation:

all cells with the same letter can be reached at the same cost d. For each such cell, if d improves its distance, update it and push it to the front of the deque. Mark the letter as used immediately after expansion. 8. Continue until all reachable states are processed. 9. The answer is dist[m-1][n-1], or -1 if it remains infinity.

Why it works

The algorithm maintains the invariant that whenever a cell is popped from the deque, its stored distance is the minimum possible distance to reach it. Teleportation edges are treated as zero-cost relaxations applied exactly once per letter, ensuring correctness without redundant processing. This effectively simulates Dijkstra’s algorithm optimized for edge weights of 0 and 1.

Python Solution

from collections import deque
from typing import List, Tuple
from collections import deque, defaultdict
from typing import List

class Solution:
    def minMoves(self, matrix: List[str]) -> int:
        m, n = len(matrix), len(matrix[0])
        portals = {}
        
        # Build portal mapping
        for i in range(m):
            for j in range(n):
                cell = matrix[i][j]
                if 'A' <= cell <= 'Z':
                    portals.setdefault(cell, []).append((i, j))
        
        queue = deque([(0, 0, 0)])  # (x, y, distance)
        visited = set([(0, 0)])
        used_portals = set()
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while queue:
            x, y, dist = queue.popleft()
            
            if (x, y) == (m-1, n-1):
                return dist
            
            # Explore neighbors
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] != '#' and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, dist + 1))
            
            # Teleportation
            cell = matrix[x][y]
            if 'A' <= cell <= 'Z' and cell not in used_portals:
                used_portals.add(cell)
                for px, py in portals[cell]:
                    if (px, py) not in visited:
                        visited.add((px, py))
                        queue.append((px, py, dist))
        
        return -1

The code first maps all portal positions, then runs a BFS with orthogonal moves. Teleportation is handled by enqueuing all other portal positions if the portal has not yet been used. The visited set prevents revisiting cells and ensures minimal moves.

    portals = defaultdict(list)
    for i in range(m):
        for j in range(n):
            ch = matrix[i][j]
            if ch.isalpha():
                portals[ch].append((i, j))

    INF = float('inf')
    dist = [[INF] * n for _ in range(m)]
    dist[0][0] = 0

    dq = deque()
    dq.append((0, 0))

    used = set()

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while dq:
        r, c = dq.popleft()
        d = dist[r][c]

        if d != dist[r][c]:
            continue

        if r == m - 1 and c == n - 1:
            return d

        ch = matrix[r][c]
        if ch.isalpha() and ch not in used:
            used.add(ch)
            for nr, nc in portals[ch]:
                if dist[nr][nc] > d:
                    dist[nr][nc] = d
                    dq.appendleft((nr, nc))

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] != '#':
                if dist[nr][nc] > d + 1:
                    dist[nr][nc] = d + 1
                    dq.append((nr, nc))

    return -1

### Implementation Explanation

The solution begins by preprocessing all portal locations into a dictionary so that teleportation lookups are O(1) per letter. The `dist` matrix tracks shortest known distances and ensures we only process improvements.

The deque implements 0-1 BFS behavior: zero-cost teleportation edges are pushed to the front, while normal movement edges are pushed to the back. This preserves correct processing order of increasing distance.

The `used` set ensures each portal letter is expanded only once, preventing repeated O(k) scans of the same portal group. This is critical for efficiency when many cells share the same letter.

The early exit condition when reaching the bottom-right cell ensures we stop as soon as the optimal path is found.

## Go Solution

```go
package main

import "container/list"

func minMoves(matrix []string) int {
    m, n := len(matrix), len(matrix[0])
    portals := map[byte][][2]int{}
    
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            cell := matrix[i][j]
            if cell >= 'A' && cell <= 'Z' {
                portals[cell] = append(portals[cell], [2]int{i, j})
            }
        }
    }
    
    type Node struct {
        x, y, dist int
    }
    
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    visited[0][0] = true
    
    usedPortals := map[byte]bool{}
    directions := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
    
    q := list.New()
    q.PushBack(Node{0, 0, 0})
    
    for q.Len() > 0 {
        front := q.Remove(q.Front()).(Node)
        x, y, dist := front.x, front.y, front.dist
        if x == m-1 && y == n-1 {
            return dist
        }
        
        // Explore neighbors
        for _, d := range directions {
            nx, ny := x+d[0], y+d[1]
            if nx >=0 && nx < m && ny >=0 && ny < n && matrix[nx][ny] != '#' && !visited[nx][ny] {
                visited[nx][ny] = true
                q.PushBack(Node{nx, ny, dist+1})
            }
        }
        
        // Teleportation
        cell := matrix[x][y]
        if cell >= 'A' && cell <= 'Z' && !usedPortals[cell] {
            usedPortals[cell] = true
            for _, p := range portals[cell] {
                px, py := p[0], p[1]
                if !visited[px][py] {
                    visited[px][py] = true
                    q.PushBack(Node{px, py, dist})
                }
            }
        }
    }
    
    return -1
}

In Go, slices and arrays are used for visited tracking. The container/list is used for BFS. Maps are used to track portals and which have been used. Logic mirrors the Python version, but explicit struct Node stores (x, y, distance).

Worked Examples

Example 1: matrix = ["A..",".A.","..."]

Initial queue: [(0,0,0)], portals: {'A': [(0,0),(1,1)]}

Step 1: dequeue (0,0,0)

• Teleport via 'A' to (1,1)
• Add neighbors (0,1) and (1,0)

Queue: (1,1,0),(0,1,1),(1,0,1)

Step 2: dequeue (1,1,0)

• Neighbors (1,2),(2,1)
• Target (2,2) reachable in 2 moves

Return 2.

Example 2: matrix = [".#...",".#.#.",".#.#.","...#."]

BFS explores sequentially, bypassing obstacles. Teleportation is unused as no letters exist. Queue grows step by step. After 13 moves, BFS reaches (3,4). Return 13.

Complexity Analysis

| Measure | Complexity import "math"

func minMoves(matrix []string) int { m := len(matrix) n := len(matrix[0])

portals := make(map[byte][][2]int)
for i := 0; i < m; i++ {
	for j := 0; j < n; j++ {
		ch := matrix[i][j]
		if ch >= 'A' && ch <= 'Z' {
			portals[ch] = append(portals[ch], [2]int{i, j})
		}
	}
}

const INF = math.MaxInt32
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

type node struct {
	r, c int
}

dq := []node{{0, 0}}
used := make(map[byte]bool)

directions := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

for len(dq) > 0 {
	cur := dq[0]
	dq = dq[1:]
	r, c := cur.r, cur.c
	d := dist[r][c]

	if r == m-1 && c == n-1 {
		return d
	}

	ch := matrix[r][c]
	if ch >= 'A' && ch <= 'Z' && !used[ch] {
		used[ch] = true
		for _, p := range portals[ch] {
			nr, nc := p[0], p[1]
			if dist[nr][nc] > d {
				dist[nr][nc] = d
				dq = append([]node{{nr, nc}}, dq...)
			}
		}
	}

	for _, dir := range directions {
		nr, nc := r+dir[0], c+dir[1]
		if nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] != '#' {
			if dist[nr][nc] > d+1 {
				dist[nr][nc] = d + 1
				dq = append(dq, node{nr, nc})
			}
		}
	}
}

return -1

}

### Go-specific Notes

The Go version uses slices as a deque substitute, with front insertion implemented via slice prepending for teleportation edges. While less efficient than a true deque structure, it remains acceptable under constraints due to limited portal expansions. Distances are stored in a 2D slice initialized with `math.MaxInt32`, and portal usage is tracked with a map for simplicity.

## Worked Examples

### Example 1

Input:

`["A..",".A.","..."]`

Portals:

`A -> [(0,0), (1,1)]`

Initial state:

`dist[0][0] = 0`

Step 1:

At `(0,0)` distance 0, portal `A` is used.

Teleport expands `(1,1)` with cost 0.

Step 2:

From `(1,1)` at cost 0, move to `(1,2)` cost 1.

Step 3:

From `(1,2)` cost 1, move to `(2,2)` cost 2.

Final answer = 2.

### Example 2

Input:

`[".#...",".#.#.",".#.#.","...#."]`

The BFS explores corridors primarily through the bottom and right edges. No portal shortcuts exist, so all moves are standard BFS expansions with unit cost. The algorithm accumulates distance layer by layer until reaching `(3,4)` with total cost 13.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(mn) | Each cell is relaxed a constant number of times, and each portal letter is expanded once |
| Space | O(mn) | Distance matrix, portal map, and BFS structures |

The key reason the solution remains linear is that every cell is inserted into the deque at most a small constant number of times, and each portal group is processed exactly once.

## Test Cases

provided examples

assert Solution().minMoves(["A..",".A.","..."]) == 2 # basic teleport shortcut assert Solution().minMoves([".#...",".#.#.",".#.#.","...#."]) == 13 # no portals

single cell grid

assert Solution().minMoves(["."]) == 0 # start is end

blocked destination

assert Solution().minMoves(["..#", "..#", "..#"]) == -1 # unreachable target

no portals large open grid

assert Solution().minMoves(["....", "....", "....", "...."]) == 6 # straight BFS

portal but useless

assert Solution().minMoves(["A#A", "...", "A.A"]) >= 0 # still solvable, portal may or may not help

| Test | Why |
| --- | --- |
| Single cell | start equals destination |
| No path due to obstacles | validates unreachable handling |
| No portals | pure BFS correctness |
| Large open grid | verifies shortest Manhattan path |
| Portal presence | ensures teleport logic does not break correctness |

## Edge Cases

One important edge case is when the grid is a single cell. In this situation, the algorithm must immediately return zero because the start and end are identical, and no traversal is required. The initialization of `dist[0][0] = 0` naturally handles this case because the BFS loop will immediately detect the target condition.

Another edge case occurs when obstacles completely block access to the destination. Since BFS only enqueues reachable neighbors, the destination cell will remain at infinite distance. The final check correctly returns `-1` in this scenario.

A third edge case involves grids with many identical portal letters. Without careful handling, repeatedly expanding teleportation could cause severe performance degradation. The `used` set ensures each letter is expanded exactly once, preventing repeated scans of large coordinate lists and keeping runtime linear.