🌀 Beginner-Friendly Guide 'Minimum Cost Path with Teleportations' - LeetCode 3651 (C++, Python, JavaScript)

Source: Dev.to

Problem Overview

Navigating a grid is a classic coding challenge, but adding teleportation changes the game entirely.
You are given:

• A 2D grid of size m x n where each cell contains a cost.
• An integer k, the maximum number of times you can teleport.
• Two movement rules:
  1. Standard moves – right or down – which cost the value of the destination cell.
  2. Teleportation – jump to any cell whose value is ≤ the current cell’s value, costing 0.

Goal: Compute the minimum total cost to travel from the top‑left cell (0,0) to the bottom‑right cell (m‑1,n‑1).

Approach

Standard DP (no teleports)

Without teleports the problem reduces to a simple DP:

dp[i][j] = grid[i][j] + min(dp[i‑1][j], dp[i][j‑1])

Introducing Teleports

Teleporting is powerful because it costs nothing, but it can only target cells with a value not greater than the current cell’s value, and you have at most k such jumps.

We solve the problem in layers (or “rounds”) based on the number of teleports used:

1. For each teleport count t = 0 … k we maintain the cheapest cost to reach every possible cell value.
2. A suffix minimum array suf_min_f[value] stores the cheapest cost to reach any cell whose value is ≥ value. This lets us answer “Is it cheaper to teleport to a cell with value x?” in O(1).
3. While scanning the grid row‑by‑row we update:
   • standard_move – cost coming from the left or top plus the current cell’s value.
   • teleport_move – suf_min_f[x] (cost of the best reachable cell with value ≥ x).
   • The minimum of these two becomes the new cost for the current cell.
4. After processing the whole grid for a given t, we rebuild suf_min_f for the next iteration.

The algorithm stops early if suf_min_f does not change between iterations.

Complexity

• Time: O(k * m * n) – each layer scans the whole grid once.
• Space: O(mx + n) where mx is the maximum cell value (for the suffix array) plus a linear DP row.

Example

grid = [[1,3,3],
        [2,5,4],
        [4,3,5]]
k = 2

1. Start at (0,0) with cost 0.
2. Move down to (1,0) → cost 2.
3. Move right to (1,1) → cost 7.
4. Teleport from (1,1) (value 5) to (2,2) (value 5) for free.
5. Destination reached with total cost 7.

The answer is 7.

Solution Implementations

C++ (GNU‑C++17)

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();

        // Edge case: free teleport possible
        if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) return 0;

        int mx = 0;
        for (auto& row : grid)
            for (int v : row) mx = max(mx, v);

        const int INF = 2e9;
        vector<int> suf_min_f(mx + 2, INF);
        vector<int> f(n + 1, INF);

        for (int t = 0; t <= k; ++t) {
            vector<int> min_f(mx + 1, INF);
            vector<int> new_f(n + 1, INF);
            if (t == 0) new_f[1] = 0;   // start cost

            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int x = grid[i][j];
                    int standard = min(new_f[j], new_f[j + 1]) + x;
                    if (i == 0 && j == 0 && t == 0) standard = 0;
                    new_f[j + 1] = min(standard, suf_min_f[x]);
                    min_f[x] = min(min_f[x], new_f[j + 1]);
                }
            }
            f = new_f;

            // rebuild suffix minima
            vector<int> new_suf(mx + 2, INF);
            for (int v = mx; v >= 0; --v)
                new_suf[v] = min(new_suf[v + 1], min_f[v]);

            if (suf_min_f == new_suf) break;
            suf_min_f.swap(new_suf);
        }
        return f[n];
    }
};

Python 3

class Solution:
    def minCost(self, grid: list[list[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        if k > 0 and grid[0][0] >= grid[m - 1][n - 1]:
            return 0

        mx = max(max(row) for row in grid)
        INF = float('inf')
        suf_min_f = [INF] * (mx + 2)
        f = [INF] * (n + 1)

        for t in range(k + 1):
            min_f = [INF] * (mx + 1)
            new_f = [INF] * (n + 1)
            if t == 0:
                new_f[1] = 0   # start cost

            for i in range(m):
                for j in range(n):
                    x = grid[i][j]
                    standard = min(new_f[j], new_f[j + 1]) + x
                    if i == 0 and j == 0 and t == 0:
                        standard = 0
                    new_f[j + 1] = min(standard, suf_min_f[x])
                    min_f[x] = min(min_f[x], new_f[j + 1])

            f = new_f

            # rebuild suffix minima
            new_suf = [INF] * (mx + 2)
            for v in range(mx, -1, -1):
                new_suf[v] = min(new_suf[v + 1], min_f[v])

            if suf_min_f == new_suf:
                break
            suf_min_f = new_suf

        return f[n]

JavaScript (Node.js)

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var minCost = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    if (k > 0 && grid[0][0] >= grid[m - 1][n - 1]) return 0;

    let mx = 0;
    for (let row of grid)
        for (let v of row) mx = Math.max(mx, v);

    const INF = Number.MAX_SAFE_INTEGER;
    let sufMinF = new Array(mx + 2).fill(INF);
    let f = new Array(n + 1).fill(INF);

    for (let t = 0; t <= k; ++t) {
        const minF = new Array(mx + 1).fill(INF);
        const newF = new Array(n + 1).fill(INF);
        if (t === 0) newF[1] = 0;   // start cost

        for (let i = 0; i < m; ++i) {
            for (let j = 0; j < n; ++j) {
                const x = grid[i][j];
                const standard = Math.min(newF[j], newF[j + 1]) + x;
                const best = Math.min(standard, sufMinF[x]);
                newF[j + 1] = best;
                minF[x] = Math.min(minF[x], best);
            }
        }
        f = newF;

        // rebuild suffix minima
        const nextSuf = new Array(mx + 2).fill(INF);
        for (let v = mx; v >= 0; --v)
            nextSuf[v] = Math.min(nextSuf[v + 1], minF[v]);

        if (JSON.stringify(sufMinF) === JSON.stringify(nextSuf)) break;
        sufMinF = nextSuf;
    }
    return f[n];
};

Key Takeaways

• State expansion (adding a teleport count dimension) lets us reuse the same DP logic for each allowed teleport.
• Suffix minima provide O(1) queries for “cheapest cost among all cells with value ≥ x”.
• Space optimization: only the results from the previous teleport count are needed, keeping memory usage linear.

This pattern appears in many real‑world routing problems, such as delivery drones that can drive (costly) or fly between high‑altitude pads (free but limited).