You are given two integers m and n representing the number of rows and columns of a grid. Your goal is to reach cell (m - 1, n - 1). You are also given a 2D integer array penalty.
The cost to enter cell (i, j) is (i + 1) * (j + 1).
You begin at cell (0, 0) and initially pay its entrance cost. Actions performed after entering (0, 0) are numbered starting from 1.
On each action, you may move to an adjacent cell or wait in the current cell. A move follows the parity rule if:
The cost of an action is determined as follows:
penalty[i][j], where (i, j) is the cell you move from.(i, j), pay penalty[i][j].After every move or wait, the action number increases by 1. Therefore, the required parity alternates after every action, regardless of whether a penalty was paid.
Return the minimum total cost required to reach (m - 1, n - 1).
Example 1:
Input: m = 2, n = 2, penalty = [[5,3],[1,4]]
Output: 8
Explanation:
The optimal path is:
(0, 0) with entry cost (0 + 1) * (0 + 1) = 1.(1, 0) with entry cost (1 + 1) * (0 + 1) = 2.(1, 1) with entry cost (1 + 1) * (1 + 1) = 4 and an extra cost of penalty[1][0] = 1 for violating the even parity rule.Thus, the total cost is 1 + 2 + 4 + 1 = 8.
Example 2:
Input: m = 2, n = 2, penalty = [[0,7],[3,2]]
Output: 7
Explanation:
The optimal path is:
(0, 0) with entry cost (0 + 1) * (0 + 1) = 1.(0, 0) with an extra cost of penalty[0][0] = 0 to flip to even parity.(0, 1) with entry cost (0 + 1) * (1 + 1) = 2 and an extra cost of penalty[0][0] = 0 for violating the even parity rule.(1, 1) with entry cost (1 + 1) * (1 + 1) = 4.Thus, the total cost is 1 + 0 + 2 + 0 + 4 = 7.
Example 3:
Input: m = 2, n = 3, penalty = [[8,0,9],[7,4,1]]
Output: 12
Explanation:
The optimal path is:
(0, 0) with entry cost (0 + 1) * (0 + 1) = 1.(0, 1) with entry cost (0 + 1) * (1 + 1) = 2.(0, 2) with entry cost (0 + 1) * (2 + 1) = 3 and an extra cost of penalty[0][1] = 0 for violating the even parity rule.(1, 2) with entry cost (1 + 1) * (2 + 1) = 6.Thus, the total cost is 1 + 2 + 3 + 0 + 6 = 12.
Constraints:
1 <= m, n <= 1052 <= m * n <= 105penalty.length == mpenalty[i].length == n0 <= penalty[i][j] <= 105Problem Overview: You need to compute the minimum path cost while enforcing an alternating direction constraint between consecutive moves. A standard shortest path algorithm is not enough because the current state depends on both the node position and the direction used in the previous step.
Approach 1: Exhaustive DFS with Backtracking (Exponential Time)
This approach recursively explores every valid path while tracking the previously used direction. Each recursive call branches into all possible next moves that satisfy the alternating rule. You can maintain a visited set to avoid immediate cycles, but the search space still grows exponentially in dense graphs or large grids. Time complexity is O(branches^depth) and space complexity is O(depth) due to recursion stack usage. This version is mainly useful for validating correctness on very small inputs.
Approach 2: Dynamic Programming with State Compression (O(V * D + E))
You can model the problem using dynamic programming where each state stores the minimum cost to reach a node with a specific previous direction. Instead of recomputing paths repeatedly, transitions reuse previously computed states. This works well when the number of directions is fixed and small. The key insight is that reaching the same node with different previous directions represents different states and cannot be merged directly. Time complexity is O(V * D + E) and space complexity is O(V * D). This technique commonly appears with dynamic programming and constrained graph traversal problems.
Approach 3: Dijkstra on Expanded State Graph (Optimal)
The optimal solution treats every pair (node, previousDirection) as a unique graph state. Use a priority queue to always expand the currently cheapest state first. For each outgoing edge, only push transitions whose direction alternates correctly from the previous move. Since edge costs may vary, Dijkstra guarantees the globally minimum answer once a state is finalized. Time complexity is O((V * D + E) log(V * D)) and space complexity is O(V * D). This is the standard interview-ready approach for weighted constrained path problems involving graphs, shortest path, and state-based traversal.
Approach 4: 0-1 BFS Variant (When Edge Weights Are Binary)
If every move cost is either 0 or 1, you can replace the priority queue with a deque. Push zero-cost transitions to the front and unit-cost transitions to the back. The alternating-direction logic remains identical to the Dijkstra state expansion model, but runtime improves because heap operations disappear. Time complexity becomes O(V * D + E) with space complexity O(V * D). Prefer this optimization only when the weight constraints allow it.
Recommended for interviews: Start with the brute-force DFS to show you understand the alternating constraint and state dependency. Then move to the expanded-state Dijkstra solution. Interviewers typically expect the shortest path formulation because it demonstrates graph modeling skill, priority queue usage, and the ability to encode extra constraints directly into traversal state.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Backtracking | Exponential | O(depth) | Small inputs or brute-force validation |
| Dynamic Programming | O(V * D + E) | O(V * D) | Fixed direction states and reusable transitions |
| Dijkstra on State Graph | O((V * D + E) log(V * D)) | O(V * D) | General weighted shortest path case |
| 0-1 BFS | O(V * D + E) | O(V * D) | Binary edge weights only |
Practice Minimum Cost Path with Alternating Directions III with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor