-
Notifications
You must be signed in to change notification settings - Fork 4
/
MinimumPathSum.java
133 lines (114 loc) · 3.54 KB
/
MinimumPathSum.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package algorithms;
/**
* 64. Minimum Path Sum
* https://leetcode.com/problems/minimum-path-sum/
* Difficulty : Medium
* Related Topics : Array, Dynamic Programming
*
* 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:
* ___ ___ ___
* | 1 | 3 | 1 |
* --- --- ---
* | 1 | 5 | 1 |
* --- --- ---
* | 4 | 2 | 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
*
* created by Cenk Canarslan on 2021-02-08
*/
public class MinimumPathSum {
public static void main(String[] args) {
int[][] grid = new int[][]{{1,3,1},{1,5,1},{4,2,1}}; // 7
// int[][] grid = new int[][]{{1,2,3},{4,5,6}}; // 12
MinimumPathSum minimumPathSum = new MinimumPathSum();
int minPathSum = minimumPathSum.minPathSum(grid);
System.out.println("minPathSum = " + minPathSum);
int minPathSumOptimized = minimumPathSum.minPathSumOptimized(grid);
System.out.println("Optimized minPathSum = " + minPathSumOptimized);
}
/**
* Optimized solution
*
* Dynamic Programming
* Time Complexity : O(m*n)
* Space Complexity : O(1) (in-place, because we're NOT using an auxiliary DS)
*
* Runtime: 2 ms, faster than 84.01% of Java online submissions
* Memory Usage: 41.7 MB, less than 69.87% of Java online submissions
*
* @param grid
* @return
*/
public int minPathSumOptimized(int[][] grid) {
int rows = grid.length;
int columns = grid[0].length;
// fill first column with consecutive sums
for (int i = 1; i < columns; i++) {
grid[0][i] = grid[0][i-1] + grid[0][i];
}
// fill first row with consecutive sums
for (int i = 1; i < rows; i++) {
grid[i][0] = grid[i-1][0] + grid[i][0];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
grid[i][j] = grid[i][j] + Math.min(grid[i-1][j], grid[i][j-1]);
}
}
return grid[rows-1][columns-1];
}
/**
* Dynamic Programming
* Time Complexity : O(m*n)
* Space Complexity : O(m*n) (not-in-place, because we're using an auxiliary DS)
*
* Runtime: 2 ms, faster than 84.01% of Java online submissions
* Memory Usage: 42 MB, less than 28.99% of Java online submissions
*
* @param grid
* @return
*/
public int minPathSum(int[][] grid) {
int rows = grid.length;
int columns = grid[0].length;
int[][] aux = new int[rows][columns];
// fill starting cell in aux
aux[0][0] = grid[0][0];
// fill first column with consecutive sums
for (int i = 1; i < columns; i++) {
aux[0][i] = aux[0][i-1] + grid[0][i];
}
// fill first row with consecutive sums
for (int i = 1; i < rows; i++) {
aux[i][0] = aux[i-1][0] + grid[i][0];
}
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
aux[i][j] = grid[i][j] + Math.min(aux[i-1][j], aux[i][j-1]);
}
}
return aux[rows-1][columns-1];
}
}