Minimum Falling Path Sum | Recursion | Memo | Bottom Up | Leetcode 931

Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 8th Video of our Playlist  "Dynami Programming : Popular Interview Problems".In this video we will try to solve a good and famous interview problem - Minimum Falling Path Sum (Leetcode 931)
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases. 
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Minimum Falling Path Sum
Company Tags  : Google, Microsoft, Amazon, Flipkart, OLA, Goldman Sachs, MakeMyTrip, OYO Rooms, Samsung
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/minimum...
SImilar Qn  : https://leetcode.com/problems/maximum...

My DP Concepts Playlist :    • Roadmap for DP | How to Start DP ? | ...  
My Graph Concepts Playlist :    • Graph Concepts & Qns - 1 : Graph will...  
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Subscribe to my channel :    / @codestorywithmik  
Instagram :   / codestorywithmik  
Facebook :   / 100090524295846  
Twitter :   / cswithmik  


Approach 1 Summary : The approach uses a recursive function MFS with memoization to compute the minimum sum by exploring possible paths from the top row to the bottom row of the matrix. The memoization is implemented using a separate 2D vector t to store previously computed results and avoid redundant calculations. The function iterates through neighboring elements in the next row and selects the path with the minimum sum. The main function then iterates over the first row and finds the minimum falling path sum by calling the recursive function for each starting column. The final result represents the minimum sum of a falling path through the matrix.

Approach-2 Summary : The approach utilizes dynamic programming and a bottom-up approach to fill a 2D vector t with the minimum falling path sums for each element in the matrix. The initialization is done for the first row, and subsequent rows are filled by considering the minimum path sum from the previous row. The result is obtained by finding the minimum element in the last row of the matrix t. The solution efficiently computes the minimum falling path sum in a non-recursive manner, using dynamic programming to avoid redundant calculations.

Approach-3 Summary : The approach utilizes a dynamic programming technique with constant space optimization. It maintains a 1D vector prev to store the minimum falling path sum for each column in the previous row. It iterates through the rows, updating the minimum falling path sum for each element in the current row (curr) based on the values in the prev vector. The prev vector is then updated with the values of the curr vector. Finally, the result is obtained by finding the minimum element in the last row of the matrix. The solution efficiently computes the minimum falling path sum with a reduced space complexity compared to a 2D matrix.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

 Timelines
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear