aboutsummaryrefslogtreecommitdiff
path: root/other/min_falling_path_sum.rs
diff options
context:
space:
mode:
Diffstat (limited to 'other/min_falling_path_sum.rs')
-rw-r--r--other/min_falling_path_sum.rs23
1 files changed, 23 insertions, 0 deletions
diff --git a/other/min_falling_path_sum.rs b/other/min_falling_path_sum.rs
new file mode 100644
index 0000000..4b704c1
--- /dev/null
+++ b/other/min_falling_path_sum.rs
@@ -0,0 +1,23 @@
+struct Solution;
+
+impl Solution {
+ pub fn min_falling_path_sum(matrix: Vec<Vec<i32>>) -> i32 {
+ matrix.into_iter().reduce(|prev, mut curr| {
+ prev.into_iter().chain(std::iter::once(i32::MAX)).scan((i32::MAX, i32::MAX, i32::MAX), |(w1, w2, w3), c| {
+ *w1 = *w2;
+ *w2 = *w3;
+ *w3 = c;
+ Some(c.min(*w1).min(*w2))
+ }).skip(1).zip(curr.iter_mut()).for_each(|(p, c)| *c += p);
+ curr
+ }).unwrap().into_iter().min().unwrap()
+ }
+}
+
+fn main() {
+ let matrix = vec![
+ vec![2,1,3],
+ vec![6,5,4],
+ vec![7,8,9]];
+ print!("{}", Solution::min_falling_path_sum(matrix));
+}