Minimum Path Sum with Obstacles
Carry the best cost across cells.
Minimum Path Sum with Obstacles is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
From Counting to Costing
Now each cell holds a value and you want the cheapest route to the corner. The goal shifts from counting paths to minimizing a cost.
Define the State
Let dp[i][j] be the smallest total cost to reach cell (i, j). Same grid, same moves, but we track sums instead of counts.
The Transition
You take the cheaper of the two incoming neighbors, then add the current cell. That min choice is the heart of the recurrence.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Mark the Obstacles
An obstacle is a cell you cannot stand on. Give it a cost of infinity so any path through it is never the minimum.
INF = float('inf')Block It Cleanly
When the grid marks a cell blocked, just set its dp to infinity and move on. The min step naturally avoids it.
if blocked(i, j):
dp[i][j] = INF
continueGuard the Start
If the starting cell itself is blocked, there is no path at all. Check that first so you do not return a garbage cost.
Seed the First Cell
The start has no neighbors to come from, so its cost is just its own value. Set dp[0][0] before the loops run.
dp[0][0] = grid[0][0]Handle the Borders
The top row only flows from the left and the left column only from above. Treat these borders so you never read off the grid.
Infinity Propagates
Adding to infinity stays infinity, so a fully walled-off cell keeps its INF cost. Unreachable cells advertise themselves automatically.
Read the Result
The minimum cost sits in the bottom-right cell. If that value is still infinity, no valid path exists at all.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1When Greedy Fails Here
Always stepping toward the smaller neighbor can trap you. Only full DP guarantees the globally cheapest path, not a greedy peek.
Quick Check
How do you make path DP avoid a blocked cell without special-casing every neighbor?
Recap: Min Path with Obstacles
Take the cheaper neighbor plus the cell value, set blocked cells to infinity, and read the corner. INF there means no path. 🧱
Frequently asked questions
Is the “Minimum Path Sum with Obstacles” lesson free?
Yes — the full text of “Minimum Path Sum with Obstacles” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Minimum Path Sum with Obstacles”?
Carry the best cost across cells. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Minimum Path Sum with Obstacles” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Path Counting on a Grid
- Minimum Path Sum with Obstacles
- Longest Common Subsequence
- Edit Distance Step by Step