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: 7 Explanation: 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