Table of Contents: Video Setup 0:00 - 0:21 Problem Introduction 0:21 - 2:01 Walk Through Examples 2:01 - 3:33 Walking Through The Recursion 3:33 - 7:34 Time and Space Complexities 7:34 - 12:00 The Code 12:00 - 16:16 Wrap Up 16:16 - 17:00 Conclusion 17:00 - 17:34 I tried my best. Markers were dry, lighting couldn't be adjust too well since the markers wrote badly on the board (not enough ink). Been sick for the past 3 days. This will suffice for now. Any questions, put them below.
ua-cam.com/video/6m4wHF2JPII/v-deo.html Better and hindi explaination to the problem. Pls support your hindu sher bhai and show some love. why give views to him. watch the best approach on my video and pls get your friends to subscribe to my channel. Your hindu sher needs you......
Finally someone is explaining space and time complexities for all problems. If you explain the time and space complexities for all problems, one day I will donate my first month salary after getting new job to your patreon account.
Although video quality was not very good, but as usual, you draw the recursion tree step by step and then write the code and everything is just crystal clear. Please make more videos on backtracking. I must say this is probably the best channel for understanding lots of difficult programming problems.
Thanks man good info. I saw this problem almost a month ago and have been stuck trying to solve it. I watched this, n-queens, and backtracking blueprint videos once yesterday. After watching those videos I was able to sit down and solve the problem without having to memorize the solution
Hey Ben, You are a great example of "practice makes a man perfect". After seeing your teaching style in the latest video(new one) to this one( old one).
I am learning backtracking currently and after watching many videos, I came here and that's the kind of understanding I needed. Thanks :) Cool stuff...
If you are watching this and don't understand where is the backtracking while it just looks like a simple recursion - that is exactly how it looks like. It's not a backtracking problem. Ben does great videos that helped me a lot but this is not one of them. Sorry :D Keep filming man. You are doing a great job indeed.
I would like to thank you for making all these hard works videos. If I were you and having no marker to write on the board, I would probably just skip making this video. But you still made it. Keep up good things!
Hahahahaha, I remember this video. This was wayyyyyy back. Yeah. That day sucked. Half these videos I didn't wanna make. I didn't wanna make this channel. I had to. No one else would do what I envisioned. So I'm doing it.
Sir, I just wanted to know how to derive recursive formula for this question. I was unsatisfied with geeksforgeeks explanation. Thanks for making a video on non trivial problems like these.
I'm honestly not sure, I mean consider the state that the recursive frames hold, they cache current choices so iteratively we would have 1 stack variable for the current pending selection and the stack would literally hold what the recursive call stack would hold...current progress, the choice made, etc. It's been a while since I did this problem but all that happens when recursion disappears is that state management becomes very tedious.
Got a version of this question on an interview today and was able to code it up but could not, for the life of me, figure out the time complexity (*melting emoji face*)
Hi Ben! How does the code know to go from A to B after its found all the permutations for A? I understand how it works visually, but I don't understand how it works in the code.
The call stack frame that recursed into A still has the state that B is next. The call stack carries state of the function call. It is an enclosed entity with its own state and behaviour.
lovely lovey video! Thanks for introducing the N Queens video as well, really helped me out to watch that before this one. Lovely explanation. Grateful :')
Maybe I am missing something. I would say that the solution is a DFS solution and not a backtracking solution. How I could tell that? Well I don't see the "step back" action (or revert last choice) in the solution. Ben, could you clarify my doubts?
I was doing code on the same which you have described on the video but there is case where added value need to be removed. so that it will work proper and create all the possible words from the given array. Thanks for sharing your valuable knowledge. static void possibleWordsWithMobile(int[] a, String partialString, int index) { if (index == a.length) { System.out.println(partialString); return; } for (int i = 0; i < mobileAlphaWords[a[index]].length(); i++) { partialString += mobileAlphaWords[a[index]].charAt(i); possibleWordsWithMobile(a, partialString, index+1); partialString = partialString.substring(0, index); } }
Is it backtracking or simply a recursion? After each sub-problem we are guaranteed that this is the current optimal solution, it's a tail recursion. There is no need to back-off and explore other possibilities at each stack.
Thanks! Great explanation. I solved the problem using backtracking. The language is Swift (just for information). Can you please let me know the time and space complexities for this solution? Will it be the same as for the recursive solution as you explained in the video or is it different? func combinationsHelper(_ mapping: [String: [String]], _ digits: [String], _ index: Int, _ result: inout [String], _ combination: inout [String]) { if index == digits.count { result.append(combination.joined()) return } let elements = mapping[digits[index]]! for i in 0..
Another great video. I solved this problem using only recursion, but I want to try the backtracking algorithm (before I look at your answer) to see if I got the lessons of the N Queens problem down. My recursive solution is here(gist.github.com/StevenXL/bbb2db93fcc2ecda1fe220169a738f0a). If you don't mind some constructive criticism, I think in this problem you could have been more clear that the reason we are using 4 as our base instead of 3 is that we want to figure out the "worst-case scenario" for our algorithm. Our algorithm does the most work when every digit maps to four characters, hence our base of 4. In my solution, I determined the running time (though not the space complexity) using a recurrence relation, which expanded into the geometric series 4 ^ 1 + 4 ^ 2 + 4 ^ 3 ... 4 ^ n. You'll probably touch upon this in future videos since it is a common bit of math for algorithms. P.S. Keep up the great work. I think a lot of different items that I've been studying are coming together in your videos.
Table of Contents:
Video Setup 0:00 - 0:21
Problem Introduction 0:21 - 2:01
Walk Through Examples 2:01 - 3:33
Walking Through The Recursion 3:33 - 7:34
Time and Space Complexities 7:34 - 12:00
The Code 12:00 - 16:16
Wrap Up 16:16 - 17:00
Conclusion 17:00 - 17:34
I tried my best. Markers were dry, lighting couldn't be adjust too well since the markers wrote badly on the board (not enough ink). Been sick for the past 3 days. This will suffice for now. Any questions, put them below.
ua-cam.com/video/6m4wHF2JPII/v-deo.html Better and hindi explaination to the problem. Pls support your hindu sher bhai and show some love. why give views to him. watch the best approach on my video and pls get your friends to subscribe to my channel. Your hindu sher needs you......
Finally someone is explaining space and time complexities for all problems. If you explain the time and space complexities for all problems, one day I will donate my first month salary after getting new job to your patreon account.
hahaha I mean I do this every video . And...no need. Just let me know of the offer, keep the money.
Although video quality was not very good, but as usual, you draw the recursion tree step by step and then write the code and everything is just crystal clear. Please make more videos on backtracking. I must say this is probably the best channel for understanding lots of difficult programming problems.
haha thx
Thanks man good info. I saw this problem almost a month ago and have been stuck trying to solve it. I watched this, n-queens, and backtracking blueprint videos once yesterday. After watching those videos I was able to sit down and solve the problem without having to memorize the solution
nice
Hey Ben,
You are a great example of "practice makes a man perfect".
After seeing your teaching style in the latest video(new one) to this one( old one).
hahahaha, im just a dude, not perfect, pretty normal
I am learning backtracking currently and after watching many videos, I came here and that's the kind of understanding I needed. Thanks :) Cool stuff...
Sure haha
underrated channel, keep this going guys
It's just me (Ben) now, thanks
If you are watching this and don't understand where is the backtracking while it just looks like a simple recursion - that is exactly how it looks like. It's not a backtracking problem. Ben does great videos that helped me a lot but this is not one of them. Sorry :D Keep filming man. You are doing a great job indeed.
I would like to thank you for making all these hard works videos. If I were you and having no marker to write on the board, I would probably just skip making this video. But you still made it. Keep up good things!
Hahahahaha, I remember this video. This was wayyyyyy back. Yeah. That day sucked. Half these videos I didn't wanna make. I didn't wanna make this channel.
I had to. No one else would do what I envisioned.
So I'm doing it.
I think the space complexity is O(4^n * n) as there are total of 4^n mnemonics each of length n. Let me know if i am wrong.
Dude you're great. I'm downloading your thought process ;)
hahahahaha nice
what if i use two for loops instead??
Sir, I just wanted to know how to derive recursive formula for this question. I was unsatisfied with geeksforgeeks explanation. Thanks for making a video on non trivial problems like these.
I will cover problems like this here: twitter.com/thebigoguide, it's the site I'm working on
This video is fantastic! Thank you very much
sure
Would an iterative solution be possibly asked for these problems? if so, how will they be solved? As every recursive solution can be done iteratively
I'm honestly not sure, I mean consider the state that the recursive frames hold, they cache current choices so iteratively we would have 1 stack variable for the current pending selection and the stack would literally hold what the recursive call stack would hold...current progress, the choice made, etc.
It's been a while since I did this problem but all that happens when recursion disappears is that state management becomes very tedious.
Very clear explanation!!
thx
Got a version of this question on an interview today and was able to code it up but could not, for the life of me, figure out the time complexity (*melting emoji face*)
Awesome explanation man! You should create more videos like this.
working on it. thanks. you are cool.
Hi Ben! How does the code know to go from A to B after its found all the permutations for A? I understand how it works visually, but I don't understand how it works in the code.
The call stack frame that recursed into A still has the state that B is next. The call stack carries state of the function call. It is an enclosed entity with its own state and behaviour.
@@BackToBackSWEthat actually makes sense!! thank you so much!!
lovely lovey video! Thanks for introducing the N Queens video as well, really helped me out to watch that before this one. Lovely explanation. Grateful :')
sure
Best expiation ever sir.
Thank you so much for your efforts.
Great.
Thanks for the great introduction and for taking discussion so deep in terms of information.
Great work indeed.
Helpful 🙏👏👏
sure
Maybe I am missing something. I would say that the solution is a DFS solution and not a backtracking solution.
How I could tell that? Well I don't see the "step back" action (or revert last choice) in the solution.
Ben, could you clarify my doubts?
Yeah this video is old haha. Backtracking: en.wikipedia.org/wiki/Backtracking
This does not prune pathways of exploration, it is simple recursion
I was doing code on the same which you have described on the video but there is case where added value need to be removed. so that it will work proper and create all the possible words from the given array. Thanks for sharing your valuable knowledge.
static void possibleWordsWithMobile(int[] a, String partialString, int index) {
if (index == a.length) {
System.out.println(partialString);
return;
}
for (int i = 0; i < mobileAlphaWords[a[index]].length(); i++) {
partialString += mobileAlphaWords[a[index]].charAt(i);
possibleWordsWithMobile(a, partialString, index+1);
partialString = partialString.substring(0, index);
}
}
nice!
thank you sir for your detailed explanation....this is really helpful..
sure
You are awesome dude.. where are you from??? country??
America 🇺🇸🌽🚜 wassup.
Is it backtracking or simply a recursion?
After each sub-problem we are guaranteed that this is the current optimal solution, it's a tail recursion. There is no need to back-off and explore other possibilities at each stack.
Where is the code?
Do check out backtobackswe.com/platform/content
thank you
Linked to Leetcode 17
I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.
Mardokay is Indian?
He says "Theek hai".
what lol
Thanks! Great explanation.
I solved the problem using backtracking. The language is Swift (just for information). Can you please let me know the time and space complexities for this solution? Will it be the same as for the recursive solution as you explained in the video or is it different?
func combinationsHelper(_ mapping: [String: [String]], _ digits: [String], _ index: Int, _ result: inout [String], _ combination: inout [String]) {
if index == digits.count {
result.append(combination.joined())
return
}
let elements = mapping[digits[index]]!
for i in 0..
Great and not sure
Another great video. I solved this problem using only recursion, but I want to try the backtracking algorithm (before I look at your answer) to see if I got the lessons of the N Queens problem down. My recursive solution is here(gist.github.com/StevenXL/bbb2db93fcc2ecda1fe220169a738f0a). If you don't mind some constructive criticism, I think in this problem you could have been more clear that the reason we are using 4 as our base instead of 3 is that we want to figure out the "worst-case scenario" for our algorithm. Our algorithm does the most work when every digit maps to four characters, hence our base of 4. In my solution, I determined the running time (though not the space complexity) using a recurrence relation, which expanded into the geometric series 4 ^ 1 + 4 ^ 2 + 4 ^ 3 ... 4 ^ n. You'll probably touch upon this in future videos since it is a common bit of math for algorithms. P.S. Keep up the great work. I think a lot of different items that I've been studying are coming together in your videos.
great
Let's Crack FAANG
You're the best! I'm glad you beat COVID early lol
while (true) {
beSafeAndTakeItEasy();
cout >> "Thanks again!" >> endl;
}
ye