N-th Tribonacci Number | 3 Approaches | AMAZON | Leetcode 1137 | codestorywithMIK
124Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 33rd Video of our Playlist "Leetcode Easy : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve an easy but a good DP problem : N-th Tribonacci Number | 3 Approaches | AMAZON | Leetcode 1137 | 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 : N-th Tribonacci Number | 3 Approaches | AMAZON | Leetcode 1137 | codestorywithMIK
Company Tags : AMAZON
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/N-th%20Tribonacci%20Number.cpp
Leetcode Link : https://leetcode.com/problems/n-th-tribonacci-number/
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 :
Sure, here's a summary of the three approaches provided:
1. **Recursion + Memoization:**
- This approach utilizes recursion with memoization to compute the tribonacci sequence.
- It stores previously computed values in an array to avoid redundant calculations.
- Time Complexity: Without memoization - O(3^n), with memoization - O(n).
- Space Complexity: O(n) due to the memoization array.
2. **Bottom-Up Dynamic Programming:**
- This approach uses bottom-up dynamic programming to compute the tribonacci sequence iteratively.
- It fills an array with the tribonacci numbers from the bottom up, starting from the base cases.
- Time Complexity: O(n) since it iterates through the sequence once.
- Space Complexity: O(1) since it only requires a constant-size array.
3. **Constant Space:**
- This approach optimizes the space complexity by maintaining only three variables.
- It iterates through the sequence, updating the variables to compute the next tribonacci number.
- Time Complexity: O(n) since it iterates through the sequence once.
- Space Complexity: O(1) since it only uses a constant amount of space.
Each approach has its advantages and disadvantages. The recursion with memoization approach trades off space for potentially faster computations, while the constant space approach optimizes space but may be less intuitive. The bottom-up dynamic programming approach strikes a balance between the two, offering both efficiency and moderate space usage.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ 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 #newyear2024