Is Minimum Cost Path With At Most K Turns easy or hard?

It is a hard problem. The 53.9% acceptance rate suggests that while the concept is approachable, correctly encoding the turn count into Dijkstra's state is easy to mess up. It shows the interviewer that you can expand classic algorithms to handle additional constraints.

Minimum Cost Path With At Most K Turns Python/Java solution

In Python use `heapq` and in Java use `PriorityQueue` to implement the Dijkstra state graph. Start from (0,0) with all four initial directions, relax neighbors, and increment the turn count only when the direction changes. Return the first popped destination state.

How to solve Minimum Cost Path With At Most K Turns in O(n)?

There is no O(n) or O(m*n) solution for the general problem because the state space is inherently 4-dimensional. The Dijkstra approach is effectively near-linear in the number of states, O(m*n*K*4 log(m*n*K*4)), which is optimal for non-negative arbitrary weights.

What is the best approach for Minimum Cost Path With At Most K Turns?

The best approach is Dijkstra's algorithm on an augmented state graph where each state is (row, col, direction, turnsUsed). This correctly handles the turn constraint while working with arbitrary non-negative cell costs. It runs in O(m*n*K*4 log(m*n*K*4)) time and O(m*n*K*4) space.

Is Minimum Cost Path With At Most K Turns asked at Google/Amazon/Meta?

Yes, this is a known hard graph problem that appears in interviews at companies like Google, Amazon, and Meta. The core skill tested is transforming a stateful constraint into a shortest-path graph and then applying Dijkstra correctly.

What data structure is used in Minimum Cost Path With At Most K Turns?

A priority queue (min-heap) is essential. Each entry stores the current total cost and a state tuple (row, col, direction, turnsUsed). You also need a 4D distance array to track the best cost reached for each state.

What is the time complexity of Minimum Cost Path With At Most K Turns?

The optimal Dijkstra-based solution has time complexity O(m*n*K*4 log(m*n*K*4)) and space complexity O(m*n*K*4). Brute-force DFS is exponential at O(4^(m*n)), so it is unusable for real inputs.

Description Hints 5 Video 49:23

4046. Minimum Cost Path With At Most K Turns

Hard53.9% acceptance

You are given a 2D integer array grid of size m x n, where grid[i][j] represents the cost of visiting cell (i, j), and an integer k.

You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1).

From each cell, you may move one step in any of the four directions: up, down, left, or right.

The cost of a path is the sum of the values of all visited cells, including the starting and ending cells. If a cell is visited more than once, its value is included each time it is visited.

Return the minimum possible path cost to reach (m - 1, n - 1) using at most k turns. If no such path exists, return -1.

A turn occurs when the direction changes between two consecutive moves. For example, moving right and then down counts as one turn, while moving right and then right does not.

Example 1:

Input: grid = [[2,7,3],[1,4,5]], k = 1

Output: 12

Explanation:

An optimal path is (0, 0) → (1, 0) → (1, 1) → (1, 2). The moves are down, right, right.
The direction changes from down to right once, so the path uses exactly k = 1 turn.
The total path cost is 2 + 1 + 4 + 5 = 12.

Example 2:

Input: grid = [[4,1,9],[3,2,5],[4,8,6]], k = 2

Output: 20

Explanation:

An optimal path is (0, 0) → (1, 0) → (1, 1) → (1, 2) → (2, 2). The moves are down, right, right, down.
The direction changes from down to right and from right to down, so the path uses exactly k = 2 turns.
The total path cost is 4 + 3 + 2 + 5 + 6 = 20.

Example 3:

Input: grid = [[1,9],[3,4]], k = 0

Output: -1

Explanation:

It is impossible to reach (1, 1) using k = 0 turns. Thus, the answer is -1.

Constraints:

1 <= m == grid.length <= 75
1 <= n == grid[i].length <= 75
0 <= grid[i][j] <= 1000
0 <= k < min(m, n)

Topics

Hints open one at a time

Hint 1

1a (Dynamic Programming). Track the minimum cost for each cell, number of turns used, and direction of the last move. Initialize paths with no turns by moving straight from the starting cell.

Hint 2

1b (Dynamic Programming). To arrive at a cell in direction d, either continue in direction d without adding a turn, or change from another direction and add one turn.

Hint 3

1c (Dynamic Programming). Process turn counts in increasing order. For each direction, sweep the grid in that direction so that straight-move transitions use states already computed in the current layer. This gives O(m * n * (k + 1)) time.

Hint 4

2a (Dijkstra). Treat each combination of cell, last move direction, and number of turns used as a shortest-path state. A move costs the value of the destination cell.

Hint 5

2b (Dijkstra). Changing direction adds one turn, while the first move adds none. Start with cost grid[0][0], discard states using more than k turns, and run Dijkstra's algorithm.

LanguageLoading editor…

1class Solution:
2    def minCost(self, grid: list[list[int]], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[[2,7,3],[1,4,5]]
1

Input

[[4,1,9],[3,2,5],[4,8,6]]
2

Input

[[1,9],[3,4]]
0

Your code is saved on this device.