[LeetCode-931] Minimum Falling Path Sum Optimised Solution

Intuition

In the first row, for every node there is a three path (row+1, col-1), (row+1, col), (row+1, col+1).

For Given Input

Approach

Brute force (Recursive approach):

the recursive function call will be

for every node the function call will be similar like that, here we can see, we are calling 7th node again so we can somehow optimise the repetition call, using any array, so when we visit any node and completed the calculation for that node, than we have to store the answer of that node into the array, so whenever we visit the same node again then we do not have to calculate the answer for that node which is already present into the array, just we have return the answer of that node. using this memoisation approach we can optimise our time complexity.

Using memoisation technique the time complexity will we O(m*n) where n and m are row, and column of matrix.

Space complexity will O(n*m) to store the data of every node.

In the technique, we are taking another O(n*m) space, for each recursive call

Can we solve this problem without recursive call ??, so we can save some memory.

Answer is yes, we can solve this using iterative approach.

Iterative Approach

Every block is depends on (row+1, col-1), (row+1, col), (row+1, col+1)

iterate on all the blocks and choose minimum of all the possible values

Complexity

• Time complexity:

• O(n*m)

• Space complexity:

• O(n*m)

Code