1368. Minimum Cost to Make at Least One Valid Path in a Grid LeetCode Solution

In this guide, you will get 1368. Minimum Cost to Make at Least One Valid Path in a Grid LeetCode Solution with the best time and space complexity. The solution to Minimum Cost to Make at Least One Valid Path in a Grid problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Cost to Make at Least One Valid Path in a Grid solution in C++
4. Minimum Cost to Make at Least One Valid Path in a Grid solution in Java
5. Minimum Cost to Make at Least One Valid Path in a Grid solution in Python
6. Additional Resources

Problem Statement of Minimum Cost to Make at Least One Valid Path in a Grid

Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:

1 which means go to the cell to the right. (i.e go from grid[i][j] to grid[i][j + 1])
2 which means go to the cell to the left. (i.e go from grid[i][j] to grid[i][j – 1])
3 which means go to the lower cell. (i.e go from grid[i][j] to grid[i + 1][j])
4 which means go to the upper cell. (i.e go from grid[i][j] to grid[i – 1][j])

Notice that there could be some signs on the cells of the grid that point outside the grid.
You will initially start at the upper left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m – 1, n – 1) following the signs on the grid. The valid path does not have to be the shortest.
You can modify the sign on a cell with cost = 1. You can modify the sign on a cell one time only.
Return the minimum cost to make the grid have at least one valid path.

Example 1:

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) –> (0, 1) –> (0, 2) –> (0, 3) change the arrow to down with cost = 1 –> (1, 3) –> (1, 2) –> (1, 1) –> (1, 0) change the arrow to down with cost = 1 –> (2, 0) –> (2, 1) –> (2, 2) –> (2, 3) change the arrow to down with cost = 1 –> (3, 3)
The total cost = 3.

Example 2:

Input: grid = [[1,1,3],[3,2,2],[1,1,4]]
Output: 0
Explanation: You can follow the path from (0, 0) to (2, 2).

Example 3:

Input: grid = [[1,2],[4,3]]
Output: 1

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 100
1 <= grid[i][j] <= 4

Complexity Analysis

• Time Complexity: O(mn)
• Space Complexity: O(mn)

1368. Minimum Cost to Make at Least One Valid Path in a Grid LeetCode Solution in C++

class Solution {
 public:
  int minCost(vector<vector<int>>& grid) {
    const int m = grid.size();
    const int n = grid[0].size();
    vector<vector<int>> mem(m, vector<int>(n, -1));
    queue<pair<int, int>> q;

    dfs(grid, 0, 0, /*cost=*/0, q, mem);

    for (int cost = 1; !q.empty(); ++cost)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        for (const auto& [dx, dy] : dirs)
          dfs(grid, i + dx, j + dy, cost, q, mem);
      }

    return mem.back().back();
  }

 private:
  static constexpr int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

  void dfs(const vector<vector<int>>& grid, int i, int j, int cost,
           queue<pair<int, int>>& q, vector<vector<int>>& mem) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return;
    if (mem[i][j] != -1)
      return;

    mem[i][j] = cost;
    q.emplace(i, j);
    const auto& [dx, dy] = dirs[grid[i][j] - 1];
    dfs(grid, i + dx, j + dy, cost, q, mem);
  }
};
/* code provided by PROGIEZ */

1368. Minimum Cost to Make at Least One Valid Path in a Grid LeetCode Solution in Java

class Solution {
  public int minCost(int[][] grid) {
    final int m = grid.length;
    final int n = grid[0].length;
    int[][] mem = new int[m][n];
    Arrays.stream(mem).forEach(A -> Arrays.fill(A, -1));
    Queue<Pair<Integer, Integer>> q = new ArrayDeque<>();

    dfs(grid, 0, 0, /*cost=*/0, q, mem);

    for (int cost = 1; !q.isEmpty(); ++cost)
      for (int sz = q.size(); sz > 0; --sz) {
        Pair<Integer, Integer> pair = q.poll();
        final int i = pair.getKey();
        final int j = pair.getValue();
        for (int[] dir : dirs)
          dfs(grid, i + dir[0], j + dir[1], cost, q, mem);
      }

    return mem[m - 1][n - 1];
  }

  private static final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

  private void dfs(int[][] grid, int i, int j, int cost, Queue<Pair<Integer, Integer>> q,
                   int[][] mem) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return;
    if (mem[i][j] != -1)
      return;

    mem[i][j] = cost;
    q.add(new Pair<>(i, j));
    int[] dir = dirs[grid[i][j] - 1];
    dfs(grid, i + dir[0], j + dir[1], cost, q, mem);
  }
}
// code provided by PROGIEZ

1368. Minimum Cost to Make at Least One Valid Path in a Grid LeetCode Solution in Python

class Solution:
  def minCost(self, grid: list[list[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    dp = [[-1] * n for _ in range(m)]
    q = collections.deque()

    def dfs(i: int, j: int, cost: int) -> None:
      if i < 0 or i == m or j < 0 or j == n:
        return
      if dp[i][j] != -1:
        return
      dp[i][j] = cost
      q.append((i, j))
      dx, dy = dirs[grid[i][j] - 1]
      dfs(i + dx, j + dy, cost)

    dfs(0, 0, 0)

    cost = 0
    while q:
      cost += 1
      for _ in range(len(q)):
        i, j = q.popleft()
        for dx, dy in dirs:
          dfs(i + dx, j + dy, cost)

    return dp[-1][-1]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.