Minimum Cost Path with Teleportations - Solution & Explanation

Problem Overview: You are given a cost matrix where moving through cells accumulates cost, but certain cells allow teleportation to other positions. The goal is to reach the destination with the minimum possible total cost while accounting for both normal moves and teleport transitions.

Approach 1: Brute Force DFS with Backtracking (Exponential Time, O(2^(mn)) time, O(mn) space)

The most direct approach explores every possible path from the start cell to the destination. From each cell you recursively try all valid directions and any teleportation options. You maintain the running path cost and track the minimum cost found. This approach demonstrates the full search space but quickly becomes infeasible because the number of paths grows exponentially with grid size. Space complexity is O(mn) due to the recursion stack and visited tracking.

Approach 2: DFS with Memoization (Top-Down Dynamic Programming) (O(mn * k) time, O(mn) space)

You can eliminate repeated work by caching results for each cell. Instead of recomputing the minimum cost from the same position multiple times, store the result in a DP table. When recursion revisits that cell, return the cached value immediately. Teleportation transitions are handled as additional edges in the recursion. This turns the brute force search into a dynamic programming problem over the grid state space. The complexity becomes O(mn * k), where k represents teleport destinations associated with a cell.

Approach 3: DP with Teleport Mapping and Dijkstra (Optimal) (O(mn log(mn)) time, O(mn) space)

The grid can be modeled as a weighted graph where each cell is a node. Adjacent moves add cost equal to the destination cell, and teleportation creates additional edges connecting distant cells. Running Dijkstra’s algorithm from the start ensures the minimum cost to each cell is processed in increasing order. A priority queue always expands the cheapest state first. To keep teleport operations efficient, group teleport cells using a hash map keyed by teleport identifier stored in an array or grid structure. Each teleport group is processed once to avoid redundant edges.

This approach works well because every grid transition becomes a simple edge relaxation. The algorithm iterates through neighbors in the matrix, pushes candidate states into the priority queue, and updates the distance table when a cheaper path is discovered. The final DP table stores the minimum cost for every cell.

Recommended for interviews: Interviewers usually expect the graph-based dynamic programming solution. Modeling the grid as a weighted graph and applying Dijkstra shows strong understanding of dynamic programming and shortest path techniques. Mentioning the brute force search first demonstrates you understand the problem space, while the optimized DP/priority-queue solution shows practical algorithm design.