-
Notifications
You must be signed in to change notification settings - Fork 0
/
minimum_path_sum.js
28 lines (24 loc) · 951 Bytes
/
minimum_path_sum.js
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
/**
* @param {number[][]} grid
* @return {number}
*/
const minPathSum = grid => {
const leastPath = grid.reduce((acc, row, i) => {
if (i == 0) {
const newAcc = row.reduce((sumAcc, value, i) => {
if (sumAcc.length == 0) return [...sumAcc, value]
return [...sumAcc, value + sumAcc[sumAcc.length - 1]]
}, [])
return newAcc
}
const newAcc = row.reduce((sumAcc, value, i) => {
if (i == 0) return [value + sumAcc[0], ...sumAcc.slice(1)]
const minimumPath = sumAcc[i] < sumAcc[i - 1] ? sumAcc[i] : sumAcc[i - 1]
const newPath = minimumPath + value
if (i == sumAcc.length - 1) return [...sumAcc.slice(0, -1), newPath]
return [...sumAcc.slice(0, i), minimumPath + value, ...sumAcc.slice(i + 1)]
}, acc)
return newAcc
}, [])
return leastPath[leastPath.length - 1]
}