Table of Contents

# Minimum Path Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Given a `m x n`

`grid`

filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

**Note:** You can only move either down or right at any point in time.

**Example 1:**

Input:grid = [[1,3,1],[1,5,1],[4,2,1]]Output:7Explanation:Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

**Example 2:**

Input:grid = [[1,2,3],[4,5,6]]Output:12

**Constraints:**

`m == grid.length`

`n == grid[i].length`

`1 <= m, n <= 200`

`0 <= grid[i][j] <= 100`

# C++ Minimum Path Sum LeetCode Solution

```
``````
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<int> cur(m, grid[0][0]);
for (int i = 1; i < m; i++)
cur[i] = cur[i - 1] + grid[i][0];
for (int j = 1; j < n; j++) {
cur[0] += grid[0][j];
for (int i = 1; i < m; i++)
cur[i] = min(cur[i - 1], cur[i]) + grid[i][j];
}
return cur[m - 1];
}
};
```

# Java Minimum Path Sum LeetCode Solution

```
``````
public static int minPathSum(int[][] grid) {
int height = grid.length;
int width = grid[0].length;
return min(grid, height - 1, width - 1);
}
public static int min(int[][]grid, int row, int col){
if(row == 0 && col == 0) return grid[row][col]; // this is the exit of the recursion
if(row == 0) return grid[row][col] + min(grid, row, col - 1); /** when we reach the first row, we could only move horizontally.*/
if(col == 0) return grid[row][col] + min(grid, row - 1, col); /** when we reach the first column, we could only move vertically.*/
return grid[row][col] + Math.min(min(grid, row - 1, col), min(grid, row, col - 1)); /** we want the min sum path so we pick the cell with the less value */
}
```

# Python 3 Minimum Path Sum LeetCode Solution

```
``````
def minPathSum(self, grid):
m = len(grid)
n = len(grid[0])
for i in range(1, n):
grid[0][i] += grid[0][i-1]
for i in range(1, m):
grid[i][0] += grid[i-1][0]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[-1][-1]
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below