Facebook Pixel

1810. Minimum Path Cost in a Hidden Grid 🔒

MediumDepth-First SearchBreadth-First SearchGraphArrayInteractiveMatrixShortest PathHeap (Priority Queue)
Leetcode Link

Problem Description

This is an interactive problem where you need to guide a robot through a hidden grid from its starting position to a target cell with minimum total cost.

The grid has the following properties:

  • Size is m x n (unknown to you)
  • Each cell is either empty (passable) or blocked
  • Each empty cell has a cost that you pay when moving to it
  • The starting cell and target cell are guaranteed to be different and not blocked
  • The starting cell's cost is not counted

You interact with the grid through a GridMaster object that provides three methods:

  • canMove(direction): Returns true if the robot can move in the given direction ('U', 'D', 'L', 'R' for up, down, left, right)
  • move(direction): Moves the robot in that direction and returns the cost of the new cell. Returns -1 if the move is invalid (blocked or out of bounds) and the robot stays in place
  • isTarget(): Returns true if the robot is currently at the target cell

Your task is to find the minimum total cost path from the starting position to the target cell. Return -1 if no valid path exists.

The challenge is that you don't know:

  • The grid dimensions
  • The starting position
  • The target position
  • The grid layout

You must explore the grid using the provided methods to discover the layout, find the target, and calculate the minimum cost path.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The problem involves a grid where the robot moves between cells. A grid is a special type of graph where each cell is a node and adjacent cells are connected by edges.

Is it a tree?

  • No: The grid structure is not a tree. It can have cycles (you can move in a square pattern and return to the same cell), and cells can have multiple paths between them.

Is the problem related to directed acyclic graphs?

  • No: The grid allows bidirectional movement (if you can move from A to B, you can move back from B to A), and it contains cycles.

Is the problem related to shortest paths?

  • Yes: The core objective is to find the minimum total cost path from the starting position to the target cell, which is a shortest path problem with weighted edges (each cell has a cost).

Is the graph weighted?

  • Yes: Each cell has an associated cost that you must pay when moving to it. These costs act as edge weights in the graph representation.

Dijkstra's Algorithm

  • The flowchart leads us to Dijkstra's Algorithm for finding the shortest path in a weighted graph.

Additional consideration for DFS: The solution actually uses DFS first for exploration phase. Since the grid is hidden and we need to discover it before finding the shortest path, DFS is used to:

  1. Explore the entire reachable grid from the starting position
  2. Build a map of the grid with cell costs
  3. Locate the target cell

After the DFS exploration phase completes, Dijkstra's algorithm (implemented using a priority queue) finds the minimum cost path from start to target.

Conclusion: The flowchart correctly identifies this as a weighted shortest path problem, suggesting Dijkstra's Algorithm. The solution combines DFS for grid exploration with Dijkstra's for finding the minimum cost path.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we're dealing with a "hidden" grid - we can't see the entire map upfront, but we can explore it step by step. This is like being in a dark maze with a flashlight that only reveals adjacent rooms.

Since we don't know where the target is or what the grid looks like, we need to solve this problem in two phases:

Phase 1: Exploration (DFS) We need to map out the entire reachable grid first. DFS is perfect for this because:

  • We can systematically explore every reachable cell from our starting position
  • We need to backtrack to our current position after exploring each direction (DFS naturally handles this with recursion)
  • As we explore, we record the cost of each cell we visit and check if we've found the target

Think of it like a scout exploring unknown territory - they venture out in one direction as far as possible, marking the terrain, then return to try another direction. The move() and opposite move pattern (like moving 'U' then 'D') allows us to explore and return to our previous position.

Phase 2: Finding Minimum Cost Path (Dijkstra's) Once we have the complete map with all cell costs and know where the target is, finding the minimum cost path becomes a standard shortest path problem. We use Dijkstra's algorithm because:

  • All costs are positive (as implied by the problem)
  • We need the optimal (minimum cost) path, not just any path
  • The grid we discovered in Phase 1 can now be treated as a weighted graph

The clever part is using a large fixed-size grid (200x200) with the robot starting at position (100, 100). This ensures we have enough space to explore in any direction without worrying about array boundaries. Cells we haven't visited remain marked as -1, distinguishing them from valid cells.

If we never find the target during exploration, we return -1. Otherwise, we run Dijkstra's algorithm on our discovered map to find the minimum cost from start to target.

Learn more about Depth-First Search, Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows the two-phase approach we identified:

Initial Setup:

  • Create a 200x200 grid g initialized with -1 to represent unexplored cells
  • Start the robot at position (100, 100) in our internal representation (center of the grid to allow exploration in all directions)
  • Define direction mappings with their opposites: 'U': (-1, 0, 'D'), 'D': (1, 0, 'U'), etc.
  • Initialize target as (-1, -1) to track if we find the target

Phase 1: DFS Exploration

def dfs(i, j):
    if master.isTarget():
        target = (i, j)  # Record target position
  
    for dir, (a, b, ndir) in dirs.items():
        x, y = i + a, j + b
        if master.canMove(dir) and g[x][y] == -1:  # Can move and not visited
            g[x][y] = master.move(dir)  # Move and record cost
            dfs(x, y)  # Recursively explore
            master.move(ndir)  # Backtrack using opposite direction

The DFS function:

  • Checks if current position is the target using isTarget()
  • For each direction, checks if movement is possible with canMove()
  • Only explores unvisited cells (g[x][y] == -1)
  • Records the cost returned by move() in the grid
  • Recursively explores from the new position
  • Backtracks by moving in the opposite direction (ndir)

Phase 2: Dijkstra's Algorithm After exploration, if no target was found (target == (-1, -1)), return -1.

Otherwise, use Dijkstra's algorithm with a min-heap:

q = [(0, 100, 100)]  # (cost, row, col) - start with 0 cost at starting position
dist = [[INF] * N for _ in range(N)]  # Distance array
dist[100][100] = 0

The algorithm proceeds as:

  1. Pop the cell with minimum cost from the heap
  2. If it's the target, return the cost
  3. For each adjacent cell that was discovered during DFS (g[x][y] != -1):
    • Calculate new cost: current_cost + g[x][y]
    • If this cost is better than the recorded distance, update it
    • Push the new state (new_cost, x, y) to the heap

Key Data Structures:

  • 2D Grid g: Stores the cost of each discovered cell, -1 for unexplored
  • Min-Heap q: Priority queue for Dijkstra's algorithm, ordered by cumulative cost
  • 2D Distance Array dist: Tracks minimum cost to reach each cell
  • Direction Dictionary dirs: Maps each direction to its movement delta and opposite direction

The solution elegantly handles the unknown grid size by using a large fixed grid and starting from the center, ensuring enough space for exploration in any direction. The combination of DFS for discovery and Dijkstra's for pathfinding provides an optimal solution to this interactive problem.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small hidden grid example to illustrate the solution approach.

Hidden Grid (unknown to us initially):

[1] [2] [#]
[3] [T] [5]
[S] [4] [6]

Where S = Start, T = Target (cost 4), # = Blocked cell

Phase 1: DFS Exploration

Starting at position (100, 100) in our internal grid:

  1. Initial state: Robot at S, g[100][100] = 0 (starting cell)
  2. Check isTarget(): Returns false
  3. Try moving Up:
    • canMove('U') returns true
    • move('U') returns cost 3, robot now at cell with cost 3
    • Record g[99][100] = 3
    • Recursively explore from (99, 100)
  4. From (99, 100), try all directions:
    • Up: canMove('U') returns true, move('U') returns 1, record g[98][100] = 1
    • From (98, 100): Can't move Up (out of bounds), Left returns 2, Right is blocked
    • Backtrack to (99, 100) with move('D')
    • Right: canMove('R') returns true, move('R') returns 4, isTarget() returns true!
    • Record target = (99, 101) and g[99][101] = 4
    • Continue exploring to map remaining cells
  5. Continue DFS until all reachable cells are explored

Discovered Grid (in our internal representation):

g[98][99]=2   g[98][100]=1   g[98][101]=-1 (blocked)
g[99][99]=3   g[99][100]=3   g[99][101]=4 (target)
g[100][99]=0  g[100][100]=0  g[100][101]=4
              (start)        g[101][101]=6

Phase 2: Dijkstra's Algorithm

Now we find the minimum cost path from (100, 100) to target (99, 101):

  1. Initialize:

    • Min-heap: [(0, 100, 100)]
    • dist[100][100] = 0

  2. Process (100, 100) with cost 0:

    • Check neighbors:
      • Up (99, 100): cost = 0 + 3 = 3, update dist[99][100] = 3, push (3, 99, 100)
      • Right (100, 101): cost = 0 + 4 = 4, update dist[100][101] = 4, push (4, 100, 101)

  3. Process (99, 100) with cost 3:

    • Check neighbors:
      • Up (98, 100): cost = 3 + 1 = 4, update dist[98][100] = 4, push (4, 98, 100)
      • Left (99, 99): cost = 3 + 3 = 6, update dist[99][99] = 6, push (6, 99, 99)
      • Right (99, 101): cost = 3 + 4 = 7, update dist[99][101] = 7, push (7, 99, 101)

  4. Process (100, 101) with cost 4:

    • Check neighbors:
      • Up (99, 101): cost = 4 + 4 = 8, but dist[99][101] = 7 (already better)
      • Down (101, 101): cost = 4 + 6 = 10

  5. Process (98, 100) with cost 4:

    • Continue exploring...

  6. Process (99, 101) with cost 7:

    • This is our target! Return cost = 7

Result: Minimum cost path is S → (cost 3) → (cost 4) = total cost 7

The optimal path goes from Start up to the cell with cost 3, then right to the Target with cost 4, giving us a total cost of 3 + 4 = 7.

Solution Implementation

1from heapq import heappush, heappop
2from typing import Optional
3
4class Solution:
5    def findShortestPath(self, master: 'GridMaster') -> int:
6        """
7        Find the shortest path from starting position to target in a hidden grid.
8      
9        Strategy:
10        1. First, explore the entire reachable grid using DFS to build a map
11        2. Then use Dijkstra's algorithm to find the shortest path to target
12      
13        Returns:
14            The minimum cost to reach target, or -1 if target is unreachable
15        """
16      
17        def explore_grid(row: int, col: int) -> None:
18            """
19            DFS to explore the grid and record cell costs and target location.
20          
21            Args:
22                row: Current row position
23                col: Current column position
24            """
25            nonlocal target_position
26          
27            # Check if current position is the target
28            if master.isTarget():
29                target_position = (row, col)
30          
31            # Try moving in all four directions
32            for direction, (row_delta, col_delta, opposite_dir) in directions.items():
33                next_row = row + row_delta
34                next_col = col + col_delta
35              
36                # Check boundaries and if we can move to this cell
37                if (0 <= next_row < GRID_SIZE and 
38                    0 <= next_col < GRID_SIZE and 
39                    master.canMove(direction) and 
40                    grid[next_row][next_col] == -1):
41                  
42                    # Move to the cell and record its cost
43                    grid[next_row][next_col] = master.move(direction)
44                  
45                    # Recursively explore from the new position
46                    explore_grid(next_row, next_col)
47                  
48                    # Backtrack to original position
49                    master.move(opposite_dir)
50      
51        # Initialize constants and data structures
52        target_position = (-1, -1)  # Target coordinates, (-1, -1) if not found
53        GRID_SIZE = 200  # Maximum grid size (using center as starting point)
54        INFINITY = 0x3F3F3F3F  # Large value representing infinity
55        START_POS = 100  # Starting position in the grid (center)
56      
57        # Initialize grid with -1 (unexplored cells)
58        grid = [[-1] * GRID_SIZE for _ in range(GRID_SIZE)]
59      
60        # Direction mappings: direction -> (row_delta, col_delta, opposite_direction)
61        directions = {
62            'U': (-1, 0, 'D'),  # Up
63            'D': (1, 0, 'U'),   # Down
64            'L': (0, -1, 'R'),  # Left
65            'R': (0, 1, 'L'),   # Right
66        }
67      
68        # Phase 1: Explore the grid using DFS from starting position
69        explore_grid(START_POS, START_POS)
70      
71        # If target was not found during exploration, return -1
72        if target_position == (-1, -1):
73            return -1
74      
75        # Phase 2: Find shortest path using Dijkstra's algorithm
76        # Priority queue: (cost, row, col)
77        priority_queue = [(0, START_POS, START_POS)]
78      
79        # Distance matrix to track minimum cost to reach each cell
80        distance = [[INFINITY] * GRID_SIZE for _ in range(GRID_SIZE)]
81        distance[START_POS][START_POS] = 0
82      
83        while priority_queue:
84            current_cost, current_row, current_col = heappop(priority_queue)
85          
86            # If we reached the target, return the cost
87            if (current_row, current_col) == target_position:
88                return current_cost
89          
90            # Check all adjacent cells
91            for row_delta, col_delta, _ in directions.values():
92                next_row = current_row + row_delta
93                next_col = current_col + col_delta
94              
95                # Check if the next cell is valid and can improve the path
96                if (0 <= next_row < GRID_SIZE and 
97                    0 <= next_col < GRID_SIZE and 
98                    grid[next_row][next_col] != -1):  # Cell has been explored
99                  
100                    new_cost = current_cost + grid[next_row][next_col]
101                  
102                    # If we found a shorter path to this cell, update it
103                    if distance[next_row][next_col] > new_cost:
104                        distance[next_row][next_col] = new_cost
105                        heappush(priority_queue, (new_cost, next_row, next_col))
106      
107        # Target is unreachable (shouldn't happen if exploration found it)
108        return 0
109
1/**
2 * // This is the GridMaster's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class GridMaster {
5 *     boolean canMove(char direction);
6 *     int move(char direction);
7 *     boolean isTarget();
8 * }
9 */
10
11class Solution {
12    // Direction arrays for movement: Up, Right, Down, Left
13    private static final char[] DIRECTIONS = {'U', 'R', 'D', 'L'};
14    private static final char[] OPPOSITE_DIRECTIONS = {'D', 'L', 'U', 'R'};
15    // Direction deltas: (row, col) changes for Up, Right, Down, Left
16    private static final int[] DIRECTION_DELTAS = {-1, 0, 1, 0, -1};
17  
18    // Grid dimensions and constants
19    private static final int GRID_SIZE = 200;
20    private static final int INFINITY = 0x3f3f3f3f;
21  
22    // Grid to store cell costs (-1 means unvisited/blocked)
23    private static int[][] grid = new int[GRID_SIZE][GRID_SIZE];
24    // Distance array for Dijkstra's algorithm
25    private static int[][] distance = new int[GRID_SIZE][GRID_SIZE];
26  
27    // Target cell coordinates
28    private int[] targetPosition;
29
30    public int findShortestPath(GridMaster master) {
31        // Initialize target position as not found
32        targetPosition = new int[] {-1, -1};
33      
34        // Initialize grid and distance arrays
35        for (int row = 0; row < GRID_SIZE; row++) {
36            Arrays.fill(grid[row], -1);
37            Arrays.fill(distance[row], INFINITY);
38        }
39      
40        // Explore the grid starting from center position (100, 100)
41        exploreMaze(100, 100, master);
42      
43        // If target was not found during exploration, return -1
44        if (targetPosition[0] == -1 && targetPosition[1] == -1) {
45            return -1;
46        }
47      
48        // Run Dijkstra's algorithm to find shortest path
49        // Priority queue stores: [distance, row, col]
50        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(
51            Comparator.comparingInt(a -> a[0])
52        );
53      
54        // Start from center position with distance 0
55        priorityQueue.offer(new int[] {0, 100, 100});
56        distance[100][100] = 0;
57      
58        // Process nodes in order of increasing distance
59        while (!priorityQueue.isEmpty()) {
60            int[] current = priorityQueue.poll();
61            int currentDistance = current[0];
62            int currentRow = current[1];
63            int currentCol = current[2];
64          
65            // Check if we reached the target
66            if (currentRow == targetPosition[0] && currentCol == targetPosition[1]) {
67                return currentDistance;
68            }
69          
70            // Explore all four directions
71            for (int direction = 0; direction < 4; direction++) {
72                int nextRow = currentRow + DIRECTION_DELTAS[direction];
73                int nextCol = currentCol + DIRECTION_DELTAS[direction + 1];
74              
75                // Check if next position is valid and can improve distance
76                if (nextRow >= 0 && nextRow < GRID_SIZE && 
77                    nextCol >= 0 && nextCol < GRID_SIZE && 
78                    grid[nextRow][nextCol] != -1) {
79                  
80                    int newDistance = currentDistance + grid[nextRow][nextCol];
81                    if (distance[nextRow][nextCol] > newDistance) {
82                        distance[nextRow][nextCol] = newDistance;
83                        priorityQueue.offer(new int[] {newDistance, nextRow, nextCol});
84                    }
85                }
86            }
87        }
88      
89        // Should not reach here if target was found during exploration
90        return 0;
91    }
92
93    /**
94     * Recursively explore the maze using DFS and build the grid representation
95     * @param row Current row position
96     * @param col Current column position
97     * @param master GridMaster API to interact with the maze
98     */
99    private void exploreMaze(int row, int col, GridMaster master) {
100        // Check if current position is the target
101        if (master.isTarget()) {
102            targetPosition = new int[] {row, col};
103        }
104      
105        // Try moving in all four directions
106        for (int directionIndex = 0; directionIndex < 4; directionIndex++) {
107            char moveDirection = DIRECTIONS[directionIndex];
108            char returnDirection = OPPOSITE_DIRECTIONS[directionIndex];
109            int nextRow = row + DIRECTION_DELTAS[directionIndex];
110            int nextCol = col + DIRECTION_DELTAS[directionIndex + 1];
111          
112            // Check if we can move in this direction and haven't visited this cell yet
113            if (nextRow >= 0 && nextRow < GRID_SIZE && 
114                nextCol >= 0 && nextCol < GRID_SIZE && 
115                master.canMove(moveDirection) && 
116                grid[nextRow][nextCol] == -1) {
117              
118                // Move to the next cell and record its cost
119                grid[nextRow][nextCol] = master.move(moveDirection);
120              
121                // Recursively explore from the new position
122                exploreMaze(nextRow, nextCol, master);
123              
124                // Backtrack to the original position
125                master.move(returnDirection);
126            }
127        }
128    }
129}
130
1/**
2 * // This is the GridMaster's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class GridMaster {
5 * public:
6 *     bool canMove(char direction);
7 *     int move(char direction);
8 *     bool isTarget();
9 * };
10 */
11
12class Solution {
13private:
14    // Direction arrays for movement: Up, Right, Down, Left
15    static constexpr char DIRECTIONS[4] = {'U', 'R', 'D', 'L'};
16    static constexpr char OPPOSITE_DIRECTIONS[4] = {'D', 'L', 'U', 'R'};
17    // Direction deltas: (row, col) changes for Up, Right, Down, Left
18    static constexpr int DIRECTION_DELTAS[5] = {-1, 0, 1, 0, -1};
19  
20    // Grid dimensions and constants
21    static constexpr int GRID_SIZE = 200;
22    static constexpr int INFINITY = 0x3f3f3f3f;
23  
24    // Grid to store cell costs (-1 means unvisited/blocked)
25    int grid[GRID_SIZE][GRID_SIZE];
26    // Distance array for Dijkstra's algorithm
27    int distance[GRID_SIZE][GRID_SIZE];
28  
29    // Target cell coordinates
30    int targetRow;
31    int targetCol;
32
33public:
34    int findShortestPath(GridMaster* master) {
35        // Initialize target position as not found
36        targetRow = -1;
37        targetCol = -1;
38      
39        // Initialize grid and distance arrays
40        for (int row = 0; row < GRID_SIZE; row++) {
41            for (int col = 0; col < GRID_SIZE; col++) {
42                grid[row][col] = -1;
43                distance[row][col] = INFINITY;
44            }
45        }
46      
47        // Explore the grid starting from center position (100, 100)
48        exploreMaze(100, 100, master);
49      
50        // If target was not found during exploration, return -1
51        if (targetRow == -1 && targetCol == -1) {
52            return -1;
53        }
54      
55        // Run Dijkstra's algorithm to find shortest path
56        // Priority queue stores: {distance, row, col}
57        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
58      
59        // Start from center position with distance 0
60        pq.push({0, 100, 100});
61        distance[100][100] = 0;
62      
63        // Process nodes in order of increasing distance
64        while (!pq.empty()) {
65            vector<int> current = pq.top();
66            pq.pop();
67          
68            int currentDistance = current[0];
69            int currentRow = current[1];
70            int currentCol = current[2];
71          
72            // Check if we reached the target
73            if (currentRow == targetRow && currentCol == targetCol) {
74                return currentDistance;
75            }
76          
77            // Skip if we've already found a better path to this node
78            if (currentDistance > distance[currentRow][currentCol]) {
79                continue;
80            }
81          
82            // Explore all four directions
83            for (int direction = 0; direction < 4; direction++) {
84                int nextRow = currentRow + DIRECTION_DELTAS[direction];
85                int nextCol = currentCol + DIRECTION_DELTAS[direction + 1];
86              
87                // Check if next position is valid and can improve distance
88                if (nextRow >= 0 && nextRow < GRID_SIZE && 
89                    nextCol >= 0 && nextCol < GRID_SIZE && 
90                    grid[nextRow][nextCol] != -1) {
91                  
92                    int newDistance = currentDistance + grid[nextRow][nextCol];
93                    if (distance[nextRow][nextCol] > newDistance) {
94                        distance[nextRow][nextCol] = newDistance;
95                        pq.push({newDistance, nextRow, nextCol});
96                    }
97                }
98            }
99        }
100      
101        // Should not reach here if target was found during exploration
102        return -1;
103    }
104
105private:
106    /**
107     * Recursively explore the maze using DFS and build the grid representation
108     * @param row Current row position
109     * @param col Current column position
110     * @param master GridMaster API to interact with the maze
111     */
112    void exploreMaze(int row, int col, GridMaster* master) {
113        // Check if current position is the target
114        if (master->isTarget()) {
115            targetRow = row;
116            targetCol = col;
117        }
118      
119        // Try moving in all four directions
120        for (int directionIndex = 0; directionIndex < 4; directionIndex++) {
121            char moveDirection = DIRECTIONS[directionIndex];
122            char returnDirection = OPPOSITE_DIRECTIONS[directionIndex];
123            int nextRow = row + DIRECTION_DELTAS[directionIndex];
124            int nextCol = col + DIRECTION_DELTAS[directionIndex + 1];
125          
126            // Check if we can move in this direction and haven't visited this cell yet
127            if (nextRow >= 0 && nextRow < GRID_SIZE && 
128                nextCol >= 0 && nextCol < GRID_SIZE && 
129                master->canMove(moveDirection) && 
130                grid[nextRow][nextCol] == -1) {
131              
132                // Move to the next cell and record its cost
133                grid[nextRow][nextCol] = master->move(moveDirection);
134              
135                // Recursively explore from the new position
136                exploreMaze(nextRow, nextCol, master);
137              
138                // Backtrack to the original position
139                master->move(returnDirection);
140            }
141        }
142    }
143};
144
1/**
2 * // This is the GridMaster's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class GridMaster {
5 *     boolean canMove(char direction);
6 *     int move(char direction);
7 *     boolean isTarget();
8 * }
9 */
10
11// Direction arrays for movement: Up, Right, Down, Left
12const DIRECTIONS: string[] = ['U', 'R', 'D', 'L'];
13const OPPOSITE_DIRECTIONS: string[] = ['D', 'L', 'U', 'R'];
14
15// Direction deltas: (row, col) changes for Up, Right, Down, Left
16const DIRECTION_DELTAS: number[] = [-1, 0, 1, 0, -1];
17
18// Grid dimensions and constants
19const GRID_SIZE: number = 200;
20const INFINITY: number = 0x3f3f3f3f;
21
22// Grid to store cell costs (-1 means unvisited/blocked)
23let grid: number[][] = [];
24
25// Distance array for Dijkstra's algorithm
26let distance: number[][] = [];
27
28// Target cell coordinates
29let targetPosition: number[] = [];
30
31/**
32 * Find the shortest path from start to target in the maze
33 * @param master - GridMaster API to interact with the maze
34 * @returns The minimum cost to reach the target, or -1 if unreachable
35 */
36function findShortestPath(master: GridMaster): number {
37    // Initialize target position as not found
38    targetPosition = [-1, -1];
39  
40    // Initialize grid and distance arrays
41    grid = Array(GRID_SIZE).fill(null).map(() => Array(GRID_SIZE).fill(-1));
42    distance = Array(GRID_SIZE).fill(null).map(() => Array(GRID_SIZE).fill(INFINITY));
43  
44    // Explore the grid starting from center position (100, 100)
45    exploreMaze(100, 100, master);
46  
47    // If target was not found during exploration, return -1
48    if (targetPosition[0] === -1 && targetPosition[1] === -1) {
49        return -1;
50    }
51  
52    // Run Dijkstra's algorithm to find shortest path
53    // Priority queue stores: [distance, row, col]
54    const priorityQueue: number[][] = [];
55  
56    // Start from center position with distance 0
57    priorityQueue.push([0, 100, 100]);
58    distance[100][100] = 0;
59  
60    // Process nodes in order of increasing distance
61    while (priorityQueue.length > 0) {
62        // Sort by distance to simulate priority queue behavior
63        priorityQueue.sort((a, b) => a[0] - b[0]);
64      
65        const current = priorityQueue.shift()!;
66        const currentDistance = current[0];
67        const currentRow = current[1];
68        const currentCol = current[2];
69      
70        // Check if we reached the target
71        if (currentRow === targetPosition[0] && currentCol === targetPosition[1]) {
72            return currentDistance;
73        }
74      
75        // Explore all four directions
76        for (let direction = 0; direction < 4; direction++) {
77            const nextRow = currentRow + DIRECTION_DELTAS[direction];
78            const nextCol = currentCol + DIRECTION_DELTAS[direction + 1];
79          
80            // Check if next position is valid and can improve distance
81            if (nextRow >= 0 && nextRow < GRID_SIZE && 
82                nextCol >= 0 && nextCol < GRID_SIZE && 
83                grid[nextRow][nextCol] !== -1) {
84              
85                const newDistance = currentDistance + grid[nextRow][nextCol];
86                if (distance[nextRow][nextCol] > newDistance) {
87                    distance[nextRow][nextCol] = newDistance;
88                    priorityQueue.push([newDistance, nextRow, nextCol]);
89                }
90            }
91        }
92    }
93  
94    // Should not reach here if target was found during exploration
95    return 0;
96}
97
98/**
99 * Recursively explore the maze using DFS and build the grid representation
100 * @param row - Current row position
101 * @param col - Current column position
102 * @param master - GridMaster API to interact with the maze
103 */
104function exploreMaze(row: number, col: number, master: GridMaster): void {
105    // Check if current position is the target
106    if (master.isTarget()) {
107        targetPosition = [row, col];
108    }
109  
110    // Try moving in all four directions
111    for (let directionIndex = 0; directionIndex < 4; directionIndex++) {
112        const moveDirection = DIRECTIONS[directionIndex];
113        const returnDirection = OPPOSITE_DIRECTIONS[directionIndex];
114        const nextRow = row + DIRECTION_DELTAS[directionIndex];
115        const nextCol = col + DIRECTION_DELTAS[directionIndex + 1];
116      
117        // Check if we can move in this direction and haven't visited this cell yet
118        if (nextRow >= 0 && nextRow < GRID_SIZE && 
119            nextCol >= 0 && nextCol < GRID_SIZE && 
120            master.canMove(moveDirection) && 
121            grid[nextRow][nextCol] === -1) {
122          
123            // Move to the next cell and record its cost
124            grid[nextRow][nextCol] = master.move(moveDirection);
125          
126            // Recursively explore from the new position
127            exploreMaze(nextRow, nextCol, master);
128          
129            // Backtrack to the original position
130            master.move(returnDirection);
131        }
132    }
133}
134

Time and Space Complexity

Time Complexity: O(N²)

The algorithm consists of two main phases:

  1. DFS Exploration Phase: The DFS explores the reachable cells in the grid. In the worst case, all N×N cells could be reachable. For each cell, we check 4 directions and potentially make recursive calls. Since each cell is visited at most once (marked by g[x][y] != -1), the DFS runs in O(N²) time.

  2. Dijkstra's Shortest Path Phase: We use a min-heap based Dijkstra's algorithm to find the shortest path from the starting position to the target. In the worst case:

    • We process up to N² vertices (cells)
    • Each vertex can be pushed to the heap at most once per relaxation
    • Each heap operation (push/pop) takes O(log(N²)) = O(log N)
    • For each vertex, we check 4 neighbors

    Total: O(N² × log N) for Dijkstra's algorithm.

Since N = 200 is a constant in this implementation, and O(N² × log N) dominates O(N²), the overall time complexity is O(N² × log N). However, treating N as the actual grid dimension that could be explored, the complexity simplifies to O(N²) when considering that the log factor is relatively small.

Space Complexity: O(N²)

The space usage includes:

  • g matrix: N × N grid storing cell costs = O(N²)
  • dist matrix: N × N grid storing distances = O(N²)
  • Recursion stack for DFS: maximum depth is O(N²) in worst case
  • Priority queue: can contain at most O(N²) elements

Total space complexity is O(N²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Mark the Starting Cell as Explored

One of the most common mistakes is not properly initializing the starting cell in the grid. The starting cell should be marked as explored with cost 0, but developers often forget this crucial step.

The Problem:

# WRONG: Starting cell remains -1 (unexplored)
grid = [[-1] * GRID_SIZE for _ in range(GRID_SIZE)]
explore_grid(START_POS, START_POS)

Without marking the starting cell, Dijkstra's algorithm may treat it as unexplored and fail to properly calculate paths.

The Solution:

# CORRECT: Mark starting cell as explored with cost 0
grid = [[-1] * GRID_SIZE for _ in range(GRID_SIZE)]
grid[START_POS][START_POS] = 0  # Starting cell has cost 0
explore_grid(START_POS, START_POS)

2. Incorrect Handling of Target Position Scope

Using target_position as a local variable in the DFS function instead of properly updating the outer scope variable.

The Problem:

def explore_grid(row, col):
    if master.isTarget():
        target_position = (row, col)  # Creates local variable, doesn't update outer scope!

The Solution:

def explore_grid(row, col):
    nonlocal target_position  # Declare we're modifying the outer scope variable
    if master.isTarget():
        target_position = (row, col)

3. Not Checking if Cell Was Already Visited in DFS

Exploring the same cell multiple times can lead to infinite recursion or incorrect cost recording.

The Problem:

# WRONG: Moving without checking if cell was already explored
if master.canMove(direction):  # Missing check for grid[next_row][next_col] == -1
    grid[next_row][next_col] = master.move(direction)
    explore_grid(next_row, next_col)

The Solution:

# CORRECT: Only explore unvisited cells
if master.canMove(direction) and grid[next_row][next_col] == -1:
    grid[next_row][next_col] = master.move(direction)
    explore_grid(next_row, next_col)

4. Using Wrong Cost in Dijkstra's Algorithm

A critical mistake is using the visited check (distance[next_row][next_col] == INFINITY) instead of properly comparing costs for relaxation.

The Problem:

# WRONG: Only checking if unvisited, not if we found a better path
if distance[next_row][next_col] == INFINITY:
    distance[next_row][next_col] = new_cost
    heappush(priority_queue, (new_cost, next_row, next_col))

The Solution:

# CORRECT: Update if we found a shorter path
if distance[next_row][next_col] > new_cost:
    distance[next_row][next_col] = new_cost
    heappush(priority_queue, (new_cost, next_row, next_col))

5. Grid Size Too Small for Large Mazes

Using a grid that's too small might cause index out of bounds errors during exploration.

The Problem:

GRID_SIZE = 50  # Too small for potentially large grids
START_POS = 25  # Not enough room to explore in all directions

The Solution:

GRID_SIZE = 200  # Large enough for most practical cases
START_POS = 100  # Center position allows exploration in all directions
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How does merge sort divide the problem into subproblems?

Recommended Readings

DFS Fundamentals

https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests

BFS Fundamentals

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

Graph Fundamentals

https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More