Permutations - Leetcode 46 - Recursive Backtracking (Python)

  Рет қаралды 13,781

Greg Hogg

Greg Hogg

Күн бұрын

Пікірлер: 55
@GregHogg
@GregHogg 5 ай бұрын
Master Data Structures & Algorithms For FREE at AlgoMap.io!
@shreehari2589
@shreehari2589 8 ай бұрын
Greg you have natural talent in teaching, kindly don’t stop making videos
@GregHogg
@GregHogg 7 ай бұрын
Awe that's so sweet. Probably just practice as I've been learning and teaching for awhile now. I really appreciate it!! 😊
@jonTheDon28
@jonTheDon28 21 сағат бұрын
After watching 3 different vids for this problem, this was the only solution where the code made intuitive sense to me, thanks for this fr
@DamosyTheFreckle
@DamosyTheFreckle 3 ай бұрын
Dude I like your solutions because they are always so clean and the fact that you don't use "pythonic code" makes it so much more easier to understand. So many other people abuse python shortcuts that makes the code impossible to understand
@dabian1916
@dabian1916 4 ай бұрын
so much better than neetcode
@GabriellBP1
@GabriellBP1 4 ай бұрын
have to agree on that one
@shubhamdas9489
@shubhamdas9489 3 ай бұрын
Yeah
@Tallonest
@Tallonest 3 ай бұрын
I agree, Greg’s are so well explained.. best channel on KZbin
@nandkarthik
@nandkarthik 2 ай бұрын
Well, Neetcode solution works for both permutation I and permuation II problem though
@hariprasad_a-i4p
@hariprasad_a-i4p 8 күн бұрын
so true
@christianjt7018
@christianjt7018 4 ай бұрын
I learned backtracking thanks to you, thanks Greg!
@GregHogg
@GregHogg 4 ай бұрын
Amazing 😍😍
@AbhishekYadav-yw8kv
@AbhishekYadav-yw8kv 4 ай бұрын
such an elegant explanation. Thanks Greg!
@arthurpongsapak9756
@arthurpongsapak9756 14 күн бұрын
this solution is so much more understandable! thank you
@rathangpandit7504
@rathangpandit7504 3 ай бұрын
Finally got a hang of backtracking because of you 🙏
@slater-cguy
@slater-cguy Ай бұрын
This is a really intuitive solution, thank you!
@jz77096
@jz77096 4 ай бұрын
I think this problem is purely a test of how to code it concisely. Leetcoding to land a Meta/Google position. Gotta use code that interviewers can read... so found 3 solutions: Dupes Insertion into a growing temp linkedList Rotations Took me a couple hours to solve on my own, giving up, then looking it up.
@Zippo_1234
@Zippo_1234 4 ай бұрын
This was excellent. Thank you
@spec6459
@spec6459 2 ай бұрын
been coding for 1-2 months and im getting into these, my brain hurts
@saurabh-11a
@saurabh-11a 4 ай бұрын
Hi Greg, I could not understand how the pop is working here, once we have the first solution, I dont understand how pop is happening twice in the for loop.
@stanleyching123
@stanleyching123 4 ай бұрын
Leaving a comment here as I want to also know
@SBManukrishna-jz6ud
@SBManukrishna-jz6ud 3 ай бұрын
Hello Saurabh, Here is how pop() does the work here.After we append the first solution to ans,the control gets back to the "sol.pop()"line and we pop 3 from sol since its the last element. At this stage note that we are in the last iteration of for loop as well since x =3. So we don't have to execute anything further with backtrack() when x=3. So now we return back the sol which is [1,2] to backtrack() when x =2. Now the next line is sol.pop().So we pop 2 from sol and hence sol becomes [1].but here is the catch... now x=2 and the loop has 1 more interation for x=3 so we check if 3 is in solution and add it into sol and sol becomes [1,3], now we call backtrack() and we compare the len of sol to n which is not equal to 3 so we start the for loop afresh once again and check if 1 is in sol. Yes 1 is in sol=[1,3],but in next iteration when x=2 since 2 is not in sol, we add it to sol and add it to ans. This is how we formulate the 2nd solution. Hope you can figure out the flow for remaining solutions and hope this helped😊
@snehasrinivasan8666
@snehasrinivasan8666 Ай бұрын
​@@SBManukrishna-jz6udGreat explanation, thank you!😁
@HemanthKumar-vl9oh
@HemanthKumar-vl9oh 5 ай бұрын
Woow ! You made look so simple . Good job. Keep doing such videos
@GregHogg
@GregHogg 5 ай бұрын
Thank you!
@Steel16
@Steel16 2 ай бұрын
Wouldn't the time complexity be O(n! * n) since we're checking each time if x is not in sol?
@DinhKhoaNguyen-h8d
@DinhKhoaNguyen-h8d Ай бұрын
guess what, n! * n is n!
@Steel16
@Steel16 Ай бұрын
@@DinhKhoaNguyen-h8d It's not. If it was O(n + n!) then it would be O(n!) but O(n*n!) cannot be reduced because the growth rate is faster than O(n!) and is in a larger complexity class
@dennybjustin
@dennybjustin 2 ай бұрын
Thank you for the detailed explanation! Really appreciate your work. Recently, a company asked the Question Leetcode 1307 (cryptarithm) on my campus. Would you please consider providing a video solution for this question, in python?
@anisbhsl
@anisbhsl 2 ай бұрын
Great explanation.
@Techgether
@Techgether 2 ай бұрын
should the checking of x in sol be counted inside the time complexity? if so, this will be O(n.n!)
@omarllama
@omarllama 2 ай бұрын
Exactly, this is more like (n+1)! should have used a set() to track the parents. But since the maximum size in the problem description was 6, this makes it negligible.
@TheMadisonBluesBand
@TheMadisonBluesBand Ай бұрын
Agreed. As @omarllama said, a set() should have been used.
@ArdianUmam
@ArdianUmam 3 ай бұрын
Great explanation, thanks!
@mehraan8592
@mehraan8592 3 ай бұрын
very good explanation. thanks
@sabaokangan
@sabaokangan 8 ай бұрын
Beautiful teaching
@GregHogg
@GregHogg 8 ай бұрын
Thanks a ton!!!
@arunselvannatesan7494
@arunselvannatesan7494 Ай бұрын
Wouldn't the space complexity be exponential if we consider the recursion stack?
@saleheen12
@saleheen12 Ай бұрын
My brain hurts. Kind of understood it after watching many times
@vivek2319
@vivek2319 3 ай бұрын
Thanks
@SoraJustAGuy
@SoraJustAGuy 2 ай бұрын
thanks mate
@saurabhbhagat4528
@saurabhbhagat4528 3 ай бұрын
We can actually use a Set instead of an array for "sol", then it'd be faster to check if a number is already in the current solution
@Techgether
@Techgether 2 ай бұрын
good idea but i tried and the order of set is not preserved after insertion, at least for python wise
@TheMadisonBluesBand
@TheMadisonBluesBand Ай бұрын
@@Techgether yes that's why use array for sol and then set for visited. Then check if num is in visited, not sol
@aswination
@aswination 7 ай бұрын
Excellent video! How would the code change if there are duplicate numbers in the array?
@GregHogg
@GregHogg 7 ай бұрын
Thank you! And there's actually a problem for that, might cover it at some point :)
@isako1234
@isako1234 4 ай бұрын
its O(n! * n), because of the line: if x not in sol
@yunusemreozvarlik2906
@yunusemreozvarlik2906 4 ай бұрын
Same for the space complexity. It should be O(n! * n)
@GarouNguyen
@GarouNguyen 5 ай бұрын
bro what is if x not in sol, can you explain that I don't understand bro
@GregHogg
@GregHogg 5 ай бұрын
If we've already used the number, we don't want to use it again
@rishabkalluri662
@rishabkalluri662 5 ай бұрын
Isn't the time complexity N! * n? , checking if x in sol is n
@rishabkalluri662
@rishabkalluri662 5 ай бұрын
or copying solution before you add it is n
@vroomerlifts
@vroomerlifts 6 ай бұрын
hell yeah
@tauicsicsics
@tauicsicsics 18 күн бұрын
explanations are great but the variable namings not so great. ans and sol? both mean the same thing, it's unclear which is the final one. maybe currSubset or smth like this.
Combinations - Leetcode 77 - Recursive Backtracking (Python)
7:56
Recursive Backtracking - DSA Course in Python Lecture 14
12:58
Tuna 🍣 ​⁠@patrickzeinali ​⁠@ChefRush
00:48
albert_cancook
Рет қаралды 148 МЛН
Мен атып көрмегенмін ! | Qalam | 5 серия
25:41
BAYGUYSTAN | 1 СЕРИЯ | bayGUYS
36:55
bayGUYS
Рет қаралды 1,9 МЛН
We Attempted The Impossible 😱
00:54
Topper Guild
Рет қаралды 56 МЛН
LeetCode was HARD until I Learned these 15 Patterns
13:00
Ashish Pratap Singh
Рет қаралды 663 М.
Permutations - Leetcode 46 - Python
11:58
NeetCodeIO
Рет қаралды 40 М.
Prefix Sum in 4 minutes | LeetCode Pattern
4:13
AlgoMasterIO
Рет қаралды 8 М.
Coin Change - Leetcode 322 - Dynamic Programming (Python)
15:27
Leetcode 46. Permutations : Introduction to backtracking
10:06
ComputerBread
Рет қаралды 108 М.
Backtracking: Permutations - Leetcode 46 - Python
9:43
NeetCode
Рет қаралды 370 М.
House Robber - Leetcode 198 - Dynamic Programming (Python)
13:15
N-Queens - Backtracking - Leetcode 51 - Python
17:51
NeetCode
Рет қаралды 185 М.
8 patterns to solve 80% Leetcode problems
7:30
Sahil & Sarra
Рет қаралды 467 М.
Tuna 🍣 ​⁠@patrickzeinali ​⁠@ChefRush
00:48
albert_cancook
Рет қаралды 148 МЛН