Scale Engineer

Grid Teleportation Traversal

Med
#3163Time: O(m * n * 2^K). Each state is visited at most once. From each state, we explore a constant number of neighbors and potentially a set of teleport destinations.Space: O(m * n * 2^K), where `m` and `n` are grid dimensions and `K` is the number of unique portal types. This is prohibitively large.
Algorithms
Breadth-First Search
Data structures
ArrayHash TableMatrix

Prompt

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 <= 103
  • 1 <= n == matrix[i].length <= 103
  • matrix[i][j] is either '#', '.', or an uppercase English letter.
  • matrix[0][0] is not an obstacle.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the problem as a shortest path search on a very large state graph. A state is defined not just by the current position (row, col) but also by the set of portals that have been used, represented by a bitmask. Since moves can have a cost of 1 (standard move) or 0 (teleportation), this is a classic 0-1 shortest path problem, which can be solved efficiently using a 0-1 Breadth-First Search (BFS) with a deque.

Algorithm

  • The state of the search is defined by (row, col, mask), where (row, col) is the current cell and mask is a bitmask representing the set of portals used.
  • A distance array dist[row][col][mask] is used to store the minimum moves to reach each state, initialized to infinity.
  • A double-ended queue (deque) is used to perform a 0-1 Breadth-First Search (BFS).
  • The search starts by initializing dist[0][0][0] = 0 and adding the state (0, 0, 0) to the deque.
  • The algorithm iteratively processes states from the deque:
    • When moving to an adjacent cell, the cost increases by 1, and the new state is added to the back of the deque.
    • When teleporting, the cost is 0, the mask is updated, and the new state(s) are added to the front of the deque.
  • The final answer is the minimum distance found in dist[m-1][n-1][mask] across all possible masks.

Walkthrough

The core idea is to augment the standard grid BFS state (row, col) with a bitmask mask to keep track of used portals. The state (row, col, mask) represents being at cell (r, c) having used the portals indicated by mask.

We use a distance array dist[m][n][1 << K] (where K is the number of portal types, up to 26) to store the minimum moves to reach each state. The search proceeds as follows:

  1. Initialization: Pre-process the grid to map portal letters to indices and find their locations. Initialize dist with infinity. Set dist[0][0][0] = 0 and push (0, 0, 0) to a deque. A special check is needed if (0,0) is a portal to handle immediate teleportation.
  2. 0-1 BFS Loop: While the deque is not empty, extract the state (r, c, mask) with distance d from the front.
  3. Regular Moves (Cost 1): For each valid neighbor (nr, nc), if d + 1 < dist[nr][nc][mask], update the distance and push (nr, nc, mask) to the back of the deque.
  4. Teleportation (Cost 0): If matrix[r][c] is an unused portal L (checked via mask), calculate new_mask = mask | (1 << L). For every other cell (tr, tc) with portal L, if d < dist[tr][tc][new_mask], update its distance and push (tr, tc, new_mask) to the front of the deque.

The final answer is min(dist[m-1][n-1][mask]) over all mask. While conceptually simple, this approach is not practical due to its massive state space.

Complexity

Time

O(m * n * 2^K). Each state is visited at most once. From each state, we explore a constant number of neighbors and potentially a set of teleport destinations.

Space

O(m * n * 2^K), where `m` and `n` are grid dimensions and `K` is the number of unique portal types. This is prohibitively large.

Trade-offs

Pros

  • Conceptually simple as it's a direct extension of BFS for shortest paths.

  • Guaranteed to find the optimal solution if it runs to completion.

Cons

  • Extremely high time and space complexity, making it infeasible for the given constraints.

  • The memory required for the dist array (m * n * 2^K) would exceed typical limits for K > 15.

  • Likely to result in Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) on most platforms.

Solutions

class 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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem