DIY: Minimum Path Sum
Solve the interview question "Minimum Path Sum" in this lesson.
We'll cover the following
Problem statement
For this problem, you are given a 2D matrix of size m x n
. The matrix is filled with positive integers, which represent the cost of going from one cell in the matrix to the next. You can either go right or down in the grid. Your task is to find the optimal path whose sum will be minimum.
Constraints
m == grid.length
n == grid[i].length
1 <= m
,n <= 200
0 <= grid[i][j] <= 100
Input
The input of the function is a 2D matrix. Here is an example of the input:
[[1,3,7],[8,5,4],[4,9,1]]
Output
The function returns the bottom-right cell value of the matrix, which contains the minimum path sum. Here is the output of the input given above:
14
Coding exercise
Implement the MinPathSum(grid)
function, where grid
is a 2D matrix that represents the terrain. This function should return the minimum path sum.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.