Minimum Falling Path Sum II | 4 Approaches | Detailed Dry Run | Leetcode 1289 | codestorywithMIK
200Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 93rd Video of our Playlist "Dynamic Programming : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good DP problem based on 2-D Array : Minimum Falling Path Sum II | 4 Approaches | Detailed Dry Run | Leetcode 1289 | codestorywithMIK
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 II | 4 Approaches | Detailed Dry Run | Leetcode 1289 | codestorywithMIK
Company Tags : Google, Microsoft, Amazon, Samsung
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/Minimum%20Falling%20Path%20Sum%20II.cpp
Leetcode Link : https://leetcode.com/problems/minimum-falling-path-sum-ii/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
Here's a short summary of each approach:
**Approach-1 (Recur + Memoization)**:
- Time Complexity (T.C): O(N^3)
- Space Complexity (S.C): O(N^2)
- This approach uses recursion with memoization.
- It recursively calculates the minimum falling path sum from each cell, storing intermediate results in a memoization table.
- The memoization table avoids redundant calculations, reducing the time complexity.
- Overall, it has a high time complexity due to the recursive nature, but it improves with memoization.
**Approach-2 (Bottom Up)**:
- T.C: O(N^3)
- S.C: O(N^2)
- This approach uses dynamic programming in a bottom-up manner.
- It iterates through each cell starting from the last row and fills the memoization table (`t`) iteratively.
- It calculates the minimum falling path sum for each cell by considering the minimum values from the next row.
- Despite being bottom-up, it still has a time complexity of \( O(N^3) \) due to the nested loops.
**Approach-3 (Optimized Bottom Up)**:
- T.C: O(N^2)
- S.C: O(N^2)
- This approach optimizes the bottom-up approach by reducing the number of inner loops.
- It eliminates one inner loop by maintaining information about the two minimum columns (`nextMin1Col` and `nextMin2Col`) from the previous row.
- By utilizing this information, it calculates the minimum falling path sum for each cell in the current row efficiently.
- This optimization reduces the time complexity to \( O(N^2) \) while maintaining the same space complexity.
**Approach-4 (Space-Optimized)**:
- T.C: O(N^2)
- S.C: O(1)
- This approach further optimizes the space complexity by not using any additional memoization table.
- Instead, it dynamically updates the minimum values (`nextMin1Col` and `nextMin2Col`) while iterating through the grid.
- It directly computes the minimum falling path sum without using any extra space, resulting in constant space complexity O(1)
- Despite being space-optimized, it maintains the same time complexity as the optimized bottom-up approach.
These approaches demonstrate different trade-offs between time and space complexity, with the optimized bottom-up and space-optimized approaches providing a good balance between them.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
2:44 - Why Greedy Fails
4:23 - Intuition + Thought Process Approach 1
7:28 - Story to code for Recursion + Memo
12:40 - Coding Approach 1
19:06 - Approach-2 (Bottom Up)
31:42 - Coding Approach-2
35:05 - Approach-3 (Optimised Bottom Up)
44:54 - Coding Approach-3
52:26 - Approach-4 (Constant Space Solution)
56:39 - Coding Approach-4
#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 #newyear2024