Minimum Cost Path Right Down Diagonal
01 · Problem
You are given an m x n grid of non-negative integers where grid[i][j] is the cost of entering cell (i, j). Starting at the top-left cell (0, 0), you want to reach the bottom-right cell (m-1, n-1).
From a cell (i, j) you may move right to (i, j+1), down to (i+1, j), or diagonally down-right to (i+1, j+1). The cost of a path is the sum of every cell it visits, including the start and end cells. Return the minimum possible path cost.
02 · Examples
grid = [[1,2,3],[4,8,2],[1,5,3]]
8
Go right to (0,1), diagonally to (1,2), then down to (2,2): 1 + 2 + 2 + 3 = 8.
grid = [[1,3],[1,1]]
2
A single diagonal move from (0,0) to (1,1) costs 1 + 1 = 2.
grid = [[5]]
5
The start is also the end, so the cost is just that cell.
03 · Constraints
- 01m == grid.length, n == grid[i].length
- 021 <= m, n <= 100
- 030 <= grid[i][j] <= 1000
04 · Optimal complexity
- Time
- O(m * n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.