‹ DS&A interview · Socratic
DSA · Dynamic Programming · #124

Minimum Path Sum

Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given an `m x n` grid `grid` filled with non-negative numbers, find a path from the top-left cell to the bottom-right cell that minimizes the sum of all numbers along the path. You may only move either **down** or **right** at any point in time. Implement `minPathSum(grid)` that returns the minimum possible path sum.

Examples
  • grid = [[1,3,1],[1,5,1],[4,2,1]] → 7 — The path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.
  • grid = [[1,2,3],[4,5,6]] → 12 — The path 1 -> 2 -> 3 -> 6.
  • grid = [[5]] → 5 — Single cell: the path is just the start which is also the end.
Constraints
  • · m == grid.length
  • · n == grid[i].length
  • · 1 <= m, n <= 200
  • · 0 <= grid[i][j] <= 200
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.