3154. Find Number of Ways to Reach the K-th Stair | Time Complexity Analysis

3154. Find Number of Ways to Reach the K-th Stair | Time Complexity Analysis | No Returning DP

Рет қаралды 2,799

Күн бұрын

In this video, I'll talk about how to solve Leetcode 3154. Find Number of Ways to Reach the K-th Stair | Time Complexity Analysis | No Returning DP
Let's Connect:
📱Discord (Join Community) : / discord
📝Linkedin: / aryan-mittal-0077
📸 Instagram: / codewitharyanbhai
💻 Twitter - / aryan_mittal007
🤖 Github: github.com/ary...
About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)
✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

Пікірлер: 23

@ARYANMITTAL 4 ай бұрын

Mass Cheating in every Leetcode Contest (More shorts on this New Channel) - kzbin.infohH473URZWnk?si=VHvc-zg59h7kbR-u . . To solve it in O(32*32) time (Iterative) - leetcode.com/problems/find-number-of-ways-to-reach-the-k-th-stair/solutions/5177275/math-o-log-n/

@ardhidattatreyavarma5337 3 ай бұрын

I did the same except didn't think of the base case as you did. Awesome solution mate!

@Codingiisgreat 4 ай бұрын

I tried to solve but only 134/600 testcases passed im glad to see your solution . void func(int p,int k,int jump,int &cnt,bool down){ if(p>=k+2) return ; if(p==k) cnt++; if(p==0) down = false; if(down){ func(p - 1,k,jump,cnt,!down); func(p + pow(2,jump),k,jump+1,cnt,down); } else{ func(p + pow(2,jump),k,jump+1,cnt,!down); } return; } int waysToReachStair(int k) { int cnt = 0 ; int jump = 0 ; int p = 1 ; func(p,k,jump,cnt,true); // moving down func(p,k,jump,cnt,false); // Moving Up return cnt; }

@theexplorer9012 2 ай бұрын

maksad nhi bhulna

@ajayprabhu465 4 ай бұрын

helpfull, june july ill be grinding leetcode. If possbile make all contest discussion videos or videos on question which teach us something. Ill be waiting ,Thank you.

@ARYANMITTAL 4 ай бұрын

Yaa yaa bro, "Weekly Contest Discussion by Aryan Mittal", write this on KZbin, you will get a playlist of nearly every contest all problems discussed on our Channel 🫂

@agam3932 3 ай бұрын

Nice solution bro!! Love the little comedy moments in bw, explore more like ur ex lmaoooo

@abhinavnarula7300 4 ай бұрын

How to even think of something like at max 32 up jumps are possible and stuff?

@theLonelyBandit6984 4 ай бұрын

Can you tell why this can't be done without memorisation?

@Vishnu-it8st 4 ай бұрын

bro can u provide the link code or something asits not working

@Codingiisgreat 4 ай бұрын

Didnt understand the 32*32*32*2 can anyone help ??

@satwiktatikonda764 4 ай бұрын

aryan bro this mass cheting thing is this the case even before 2-3 yrs back

@fraserdab 4 ай бұрын

Last weekly contest ka hard ka video if possible?

@gui-codes 4 ай бұрын

It's very confusing bhai. Or I believe this is not for beginners.

@ARYANMITTAL 4 ай бұрын

Let's try again & if again, then do let me know, ki kha dikkat aati hai ❤️

@gui-codes 4 ай бұрын

@@ARYANMITTAL sure thanks bhai

@user-bh9ts7db5r 4 ай бұрын

@ARYANMITTAL class Solution { public: unordered_map m; int help( int k,int i,int j, int prev){ int c=0; if(i>k+1)return 0; if(i==k )c=1; if(m[i][j][prev]!=0)return m[i][j][prev]; int op1=0; if(i!=0 && prev!=0) op1 = help(k,i-1,j, 0); int op2 = help(k,i+pow(2,j), j+1 , 1); return m[i][j][prev] = c + op1 + op2; } int waysToReachStair(int k) { return help(k,1,0,-1); } }; Please tell me what am I doing wrong? I have memoised this but it is still giving TLEwww.youtube.com/@ARYANMITTAL

@sangdilbiswal30 4 ай бұрын

code seem correct but the check for map is incorrect m.count(i) && m[i].count(prev)&& m[i][prev].count(j) this in place of m[i][j][prev]!=0 class Solution { public: unordered_map m; int help( int &k,int i,int j, bool prev){ if(i>k+1)return 0; if( m.count(i) && m[i].count(prev)&& m[i][prev].count(j))return m[i][prev][j]; return m[i][prev][j] = ((i==k )?1:0) + ((i!=0 && prev==0)?help(k,i-1,j, 1):0) + help(k,i+(1

@sangdilbiswal30 4 ай бұрын

His code below... #define ll long long int class Solution { public: unordered_map dp; int solve( int i, int& k, int wasLastDown, int jump){ if(i>k+1)return 0; if( dp.count(i) && dp[i].count(wasLastDown)&& dp[i][wasLastDown].count(jump))return dp[i][wasLastDown][jump]; ll ans = (i==k); ans += solve(i+pow(2,jump),k,0,jump+1); if(i!= 0 && !wasLastDown) ans += solve(i-1, k, 1, jump); return dp[i][wasLastDown][jump]=ans; } int waysToReachStair(int k) { int ans = (int)solve(1,k,0,0); return (int)ans; } };