DIY: Minimum Path Sum

Solve the interview question "Minimum Path Sum" in this lesson.

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 70+ hands-on prep courses.