Skip to main content
Talentd

Minimum Cost Path with Alternating Directions II - Solution & Explanation

MediumArrayDynamic ProgrammingMatrix5 min read
Practice this problem

Problem Statement

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), paying waitCost[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), paying waitCost[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), paying waitCost[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 <= 105
  • 2 <= m * n <= 105
  • waitCost.length == m
  • waitCost[0].length == n
  • 0 <= 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS with Direction TrackingO(2^(m*n))O(m*n)Conceptual baseline or very small grids
Dynamic Programming with Direction StateO(m*n)O(m*n)General case and expected interview solution

Video Solution

Leetcode Biweekly Contest 160 - Q2. Minimum Cost Path with Alternating Directions II • ADevOpsEngineer • 406 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Cost Path with Alternating Directions II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays