Minimum Cost Path with Alternating Directions II solution and explanation
6 more videos on this problem
Leetcode Biweekly Contest 160 - Q2. Minimum Cost Path with Alternating Directions IIADevOpsEngineer · 26:51 · 406 views
Leetcode 3603 detailed explanation || Minimum Cost Path with Alternating DirectionsSamrat Bhardwaj · 17:29 · 380 views
LeetCode 3603. Minimum Cost Path with Alternating Directions II | Recusion | Memoization | MediumLeet's Code · 31:21 · 279 views
3603. Minimum Cost Path with Alternating Directions II (Leetcode Medium)Programming Live with Larry · 8:30 · 208 views
3603. Minimum Cost Path with Alternating Directions II | C++ DP Memoized 🔥|| BiWeekly 160BEASTCODES · 19:12 · 187 views
Leetcode 3603,3604|Min cost path with alternating direction|Min time to reach dest in directed graphCodeWithMeGuys · 13:06 · 187 views
LeetCode 3603 – Minimum Cost Path with Alternating Directions II | Biweekly Contest 160DesiCoding · 10:41 · 154 views
The problem
You are given two integers m and n representing the number of rows and columns of a grid, respectively.
The cost to enter cell (i, j) is defined as (i + 1) * (j + 1).
You are also given a 2D integer array waitCost where waitCost[i][j] defines the cost to wait on that cell.
The path will always begin by entering cell (0, 0) on move 1 and paying the entrance cost.
At each step, you follow an alternating pattern:
- On odd-numbered seconds, you must move right or down to an adjacent cell, paying its entry cost.
- On even-numbered seconds, you must wait in place for exactly one second and pay
waitCost[i][j]during that second.
Return the minimum total cost required to reach (m - 1, n - 1).
Example 1:
Input: m = 1, n = 2, waitCost = [[1,2]]
Output: 3
Explanation:
The optimal path is:
- Start at cell
(0, 0)at second 1 with entry cost(0 + 1) * (0 + 1) = 1. - Second 1: Move right to cell
(0, 1)with entry cost(0 + 1) * (1 + 1) = 2.
Thus, the total cost is 1 + 2 = 3.
Example 2:
Input: m = 2, n = 2, waitCost = [[3,5],[2,4]]
Output: 9
Explanation:
The optimal path is:
- Start at cell
(0, 0)at second 1 with entry cost(0 + 1) * (0 + 1) = 1. - Second 1: Move down to cell
(1, 0)with entry cost(1 + 1) * (0 + 1) = 2. - Second 2: Wait at cell
(1, 0), payingwaitCost[1][0] = 2. - Second 3: Move right to cell
(1, 1)with entry cost(1 + 1) * (1 + 1) = 4.
Thus, the total cost is 1 + 2 + 2 + 4 = 9.
Example 3:
Input: m = 2, n = 3, waitCost = [[6,1,4],[3,2,5]]
Output: 16
Explanation:
The optimal path is:
- Start at cell
(0, 0)at second 1 with entry cost(0 + 1) * (0 + 1) = 1. - Second 1: Move right to cell
(0, 1)with entry cost(0 + 1) * (1 + 1) = 2. - Second 2: Wait at cell
(0, 1), payingwaitCost[0][1] = 1. - Second 3: Move down to cell
(1, 1)with entry cost(1 + 1) * (1 + 1) = 4. - Second 4: Wait at cell
(1, 1), payingwaitCost[1][1] = 2. - Second 5: Move right to cell
(1, 2)with entry cost(1 + 1) * (2 + 1) = 6.
Thus, the total cost is 1 + 2 + 1 + 4 + 2 + 6 = 16.
Constraints:
1 <= m, n <= 1052 <= m * n <= 105waitCost.length == mwaitCost[0].length == n0 <= waitCost[i][j] <= 105
Approach overview
Problem Overview: You are given a cost matrix and need the minimum cost to travel from the top-left cell to the bottom-right cell. The constraint: consecutive moves must alternate direction types (horizontal vs vertical). Every move adds the cost of the destination cell, so the challenge is tracking both position and the last direction used.
Approach 1: Brute Force DFS with Direction Tracking (Exponential Time, O(2^(m*n)) time, O(m*n) recursion space)
Start a depth‑first search from (0,0). At each cell, try valid moves that alternate direction from the previous step. For example, if the last move was horizontal, the next must be vertical. Track visited states and accumulate path cost until reaching the bottom-right cell. This approach explores many repeated states because the same cell can be reached with different previous directions, making the runtime exponential. Useful mainly for understanding the constraint and validating small inputs.
Approach 2: Dynamic Programming with Direction State (O(m*n) time, O(m*n) space)
The key observation: the optimal cost for a cell depends on both its coordinates and the direction used to reach it. Maintain two DP states per cell: dp[i][j][0] for arriving via a horizontal move and dp[i][j][1] for arriving via a vertical move. When transitioning, enforce alternation: horizontal states transition from vertical states and vice versa. Iterate through the grid and update costs using the minimum previous valid state. Each state is processed once, giving O(m*n) time with constant work per transition.
Using a direction-aware DP avoids recomputation and models the constraint directly in the state. The idea is similar to grid problems where movement history matters, commonly solved with Dynamic Programming on a Matrix. The grid itself is treated like a graph where each cell has two directional states, a pattern also seen in constrained path problems over Array-based grids.
Recommended for interviews: The dynamic programming approach with a direction state is what interviewers expect. A brute force DFS demonstrates understanding of the alternating constraint, but the DP solution shows you can convert repeated subproblems into a state transition and reduce the complexity to linear in the number of cells.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS with Direction Tracking | O(2^(m*n)) | O(m*n) | Conceptual baseline or very small grids |
| Dynamic Programming with Direction State | O(m*n) | O(m*n) | General case and expected interview solution |
Frequently asked questions
Is Minimum Cost Path with Alternating Directions II easy or hard?
The problem is rated Medium because the grid traversal itself is straightforward, but the alternating-direction constraint requires an additional DP state. Recognizing that direction must be part of the state is the key insight.
Minimum Cost Path with Alternating Directions II Python/Java solution
Implement a DP table such as dp[m][n][2], where the third dimension tracks whether the last move was horizontal or vertical. Update states while scanning the grid and return the minimum value at the bottom-right cell.
How to solve Minimum Cost Path with Alternating Directions II in O(m*n)?
Track two DP values per cell: cost when the last move was horizontal and cost when it was vertical. When updating a state, only transition from the opposite direction state of neighboring cells. This ensures alternating movement while processing each grid cell in constant time.
What is the best approach for Minimum Cost Path with Alternating Directions II?
Dynamic programming with a direction state is the most efficient approach. Each cell stores the minimum cost for arriving via a horizontal or vertical move. Transitions only occur between opposite directions, which enforces the alternating constraint while keeping the complexity O(m*n).
Is Minimum Cost Path with Alternating Directions II asked at Google/Amazon/Meta?
Grid dynamic programming problems with movement constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving direction constraints, path costs, or state-based transitions are common in onsite algorithm rounds.
What data structure is used in Minimum Cost Path with Alternating Directions II?
The core structure is a dynamic programming table built on top of the matrix. Each cell maintains two values representing the minimum cost depending on the direction used to reach the cell.
What is the time complexity of Minimum Cost Path with Alternating Directions II?
The optimal dynamic programming solution runs in O(m*n) time where m and n are the grid dimensions. Each cell maintains two states (horizontal arrival and vertical arrival) and each transition is processed once.