/64. Minimum Path Sum

64. Minimum Path Sum

Medium
Arrays67.9% acceptance

Given a 2D array matrix of size m x n containing non-negative integers, compute the minimum sum of values along a path from the top-left cell (0,0) to the bottom-right cell (m-1,n-1). At each step, you may only move either one cell to the right or one cell down.

Example 1

Input: [[2,4,1],[3,2,5],[6,1,2]]

Output: 9

Explanation: Path: 2 → 3 → 2 → 1 → 1 (sum = 9)

Example 2

Input: [[5,1],[2,3]]

Output: 8

Explanation: Path: 5 → 1 → 3 (sum = 8)

Constraints

  • 1 <= len(matrix) <= 200
  • 1 <= len(matrix[0]) <= 200
  • 0 <= matrix[i][j] <= 200 for all valid i, j
Python (current runtime)

Case 1

Input: [[7,2,3],[1,8,1],[4,2,6]]

Expected: 14

Case 2

Input: [[0,1,2],[1,0,1],[2,1,0]]

Expected: 2

Case 3

Input: [[10]]

Expected: 10

Case 4

Input: [[1,2],[1,1]]

Expected: 3

Case 5

Input: [[3,3,3],[3,3,3],[3,3,3]]

Expected: 15