Dude. The number of leetocde solutions without explanations, but you took the time and effort to elaborate it out. You definitely deserve the best career possible. I am 10 years in the field and its rare to find people like you.
I don't think it is O(n) complexity. Looks like O(n^2) beacuse of nested while loops for the worst case. If the input string is already a valid palindrome then it will be O(n). If we don't make a isPalindrome function and put 2 while loops directly inside the top while loop then internal 2 while loops will be O(2n) and with outer while loop it will become O(n^2). Please correct me if this logic is wrong.
wrong, it is guaranteed O(N) in the worst case. When we find a mismatch, we loop through the rest of the string twice (substring from i + 1 to j, and substring from i to j - 1). If the first and last characters are mismatched, those 2 isPalindrome calls will be O(2N), and we immediately return after they are called. We NEVER call isPalindrome more than 2 times, so its guaranteed to be an O(N) solution in the worst case.
Bro i know u probably have other important things to do but can u pls make more videos quickly?i love the way u explain and want to learn more from u..maybe make 2-3 videos a day? Xd
Kevin, thanks for the great videos. I don't have Java experience, but I've been watching all your stuff because you explain in such an understandable way. You've surely been through hundreds of these problems, do you often run into a question that leaves you stumped for a bit? It would be interesting to see you code through a difficult problem for the first time. Question on prep vs. interview... when working through problems on LeetCode, I usually start small and keep iterating and executing/testing the code until i reach a satisfactory solution. Should the goal be to instead think through the problem and code the solution all in one go?
I'm having trouble solving the problem 1172. Dinner Plate Stacks from Leetcode. I don't really understand the explanation in CTCI either. A video regarding this would be much appreciated. I've spent a fair bit of time with this problem. The methods I'm having trouble with are leftShift and specially join, if you check the CTCI implementation. Thanks!
Thanks for helping us with these coding interviews. I have to take a part 2 - Amazon Full-Time SDE Assessment by this Friday. Would you give me any advice before I take it?
Of course! My advice would be... 1. stay calm! These questions can't be THAT hard if they're just a coding assessment so try to remember that when you're going through them! 2. Read up on the most asked questions on LeetCode before taking it (hopefully you've been doing this :P) 3. don't sweat it. What i mean by this is if it doesn't work out it's ok! There's tons of other incredible companies out there and you can always reapply. Remembering this tends to help me out. I hope these help and I'd love to hear how it goes tomorrow! Best of luck, you've got this!
@@psn999100 Thank you. I have been practicing in Leetcode that page is fantastic. I just barely graduated and I cant wait to learn more and more every time. Thanks for your help again I appreciate it.
Kevin .. thank you for all the wonderful videos. I was wondering if just keeping a counter on the first while loop would suffice and if the counter goes over 1 then you can return a false instead of creating another method for checking the substring for a palindrome
I could be wrong but I don't think this would work; if there was a mismatch everything subsequent to the mismatch would also be a mismatch...because the 'non palindrome' character is essentially introducing a shift...
Nice vid but im a bit confused, how does the helper method work for the inner 2 indexes? Wouldnt the indexes overlap and not not beyond the while loop?
When they give condition in the problem like Strings length is less than 50k chars etc. Do we need to explicitly add it in the code to check? Could you please explain.
No. Recursion is when you keep calling the same function over and over again (building a stack of consecutive function calls), with a different state, until you get to a base case.
Yes it can be, because actually you are solving this by doing the same thing twice but for smaller range and you can limit the number of the recursion calls by counter, here is code for it by Swift: func validPalindrome(_ s: String) -> Bool { var low = 0 var high = s.count-1 return validPalindrome(s, low, high, 0) } func validPalindrome(_ s: String, _ low: Int, _ high: Int, _ count: Int) -> Bool { if count > 1 { return false } let sChars = Array(s) var low = low var high = high while low < high { if sChars[low] == sChars[high] { low += 1 high -= 1 } else { return validPalindrome(s, low+1, high, count+1) || validPalindrome(s, low, high-1, count+1) } } return true }
Kevin Naughton Jr. interestingly the question page shows it as easy... but if you search for it in search bar on home page, by typing 680...it says hard as difficulty level...😊
For the second func chars are not compared for initial input vals i,j but are incremented right away...why is that still working I wonder. P.S awesome videos
For better understanding try to solve this little puzzle: let i = 3; i++ - i - ++i = ? (you may execute this expression manually from left to right and check yourself in a browser's console after). Enjoy! :-)
Hey Kevin, Please upload the video for longest palindrom substring Leetcode and word search II Leetcode. Can you please do it by tomorrow? Also, word search II using Trie.
![ATEEZ(에이티즈) - [GOLDEN HOUR : Part.2] Preview](http://i.ytimg.com/vi/X4PfgRPBUVo/mqdefault.jpg)
Dude. The number of leetocde solutions without explanations, but you took the time and effort to elaborate it out. You definitely deserve the best career possible. I am 10 years in the field and its rare to find people like you.
Whenever you say "pretty simple problem" I feel bad because to me it´s really hard (even though leetcode says "easy") I need more practice.
same. I solved it, but my algorithm has too much time complexity.
Keep grindin
Runtime is too strict, and edge cases are too annoying for this to be an "easy" problem.
I like the way you approach the problems.
Thanks Gokul!
Awesome explanation, even without knowing Java you make these questions super easy to understand 🙏
I was recently asked the spiral matrix question in the first round of my Facebook interview. Somehow managed to implement it.
Nice that's awesome!!!
How long did it take for you to do it ?
@Mai Hassan I've literally specified that Facebook had asked it.
@@siddhantmisra5664 You got the job?
@@unknownman1 Fortunately no.
Awesome explanation man.....you are on next level 🔥🔥🔥🔥
I was asked this question in Facebook interview.
Thank you for such a nice explaination
I don't think it is O(n) complexity. Looks like O(n^2) beacuse of nested while loops for the worst case. If the input string is already a valid palindrome then it will be O(n).
If we don't make a isPalindrome function and put 2 while loops directly inside the top while loop then internal 2 while loops will be O(2n) and with outer while loop it will become O(n^2).
Please correct me if this logic is wrong.
wrong, it is guaranteed O(N) in the worst case. When we find a mismatch, we loop through the rest of the string twice (substring from i + 1 to j, and substring from i to j - 1). If the first and last characters are mismatched, those 2 isPalindrome calls will be O(2N), and we immediately return after they are called. We NEVER call isPalindrome more than 2 times, so its guaranteed to be an O(N) solution in the worst case.
Kevin excellent explanation ..
Bro i know u probably have other important things to do but can u pls make more videos quickly?i love the way u explain and want to learn more from u..maybe make 2-3 videos a day? Xd
Haha thanks and I wish I could!
@@KevinNaughtonJr 1 year later: bro can you make at least one video? haha
just perfect explanation. Thank you!
jeezradz thanks! If you like my explanations check out the interviewing service I launched thedailybyte.dev/
I love this question
Kevin, thanks for the great videos. I don't have Java experience, but I've been watching all your stuff because you explain in such an understandable way. You've surely been through hundreds of these problems, do you often run into a question that leaves you stumped for a bit? It would be interesting to see you code through a difficult problem for the first time.
Question on prep vs. interview... when working through problems on LeetCode, I usually start small and keep iterating and executing/testing the code until i reach a satisfactory solution. Should the goal be to instead think through the problem and code the solution all in one go?
I'm having trouble solving the problem 1172. Dinner Plate Stacks from Leetcode. I don't really understand the explanation in CTCI either. A video regarding this would be much appreciated. I've spent a fair bit of time with this problem. The methods I'm having trouble with are leftShift and specially join, if you check the CTCI implementation. Thanks!
Thanks for helping us with these coding interviews. I have to take a part 2 - Amazon Full-Time SDE Assessment by this Friday. Would you give me any advice before I take it?
Leetcode Amazon Card from Leetcode Explore section
Of course! My advice would be...
1. stay calm! These questions can't be THAT hard if they're just a coding assessment so try to remember that when you're going through them!
2. Read up on the most asked questions on LeetCode before taking it (hopefully you've been doing this :P)
3. don't sweat it. What i mean by this is if it doesn't work out it's ok! There's tons of other incredible companies out there and you can always reapply. Remembering this tends to help me out.
I hope these help and I'd love to hear how it goes tomorrow! Best of luck, you've got this!
@@KevinNaughtonJr Thank you so much I appreciate it! I will do my best!
@@psn999100 Thank you. I have been practicing in Leetcode that page is fantastic. I just barely graduated and I cant wait to learn more and more every time. Thanks for your help again I appreciate it.
@@alanchavez16 You got the job?
very cool explanation! I was unnecessarily doing recursion in my helper function! This is better :)
Great video. Keep up the good work!
Thanks Jon! I'm glad you enjoyed the video!
Kevin .. thank you for all the wonderful videos.
I was wondering if just keeping a counter on the first while loop would suffice and if the counter goes over 1 then you can return a false instead of creating another method for checking the substring for a palindrome
I could be wrong but I don't think this would work; if there was a mismatch everything subsequent to the mismatch would also be a mismatch...because the 'non palindrome' character is essentially introducing a shift...
yes, i tried that approach. It didn't work. e.g "lcupuufxxfuupucul". Try checking your logic for this example.
Nice vid but im a bit confused, how does the helper method work for the inner 2 indexes? Wouldnt the indexes overlap and not not beyond the while loop?
Thanks Kevin!!
You might wanna try using a whiteboard to explain stuff.
Seems to be timing out for me, isn't it O(n^2) and not O(n) ?
definitely a tricky one!
it's tough!
Excellent thank you
Thanks alot
It runs, Awesome!!!
Thank you.
anytime!
great work!
When they give condition in the problem like Strings length is less than 50k chars etc. Do we need to explicitly add it in the code to check? Could you please explain.
Thnx Kevin. This is helpful :)
yes to the music. lol
Cool Explanation
Thanks Vinaya!
its failed for input s="cbbcc"
damn, i fell so stupid after watch this video ...
how can I check palindrome by removing at most 2/3 characters ?
having a counter and decrementing it instead of directly returning the result of isPalindrome should work
Is this solution recursion? I can see you return one method inside another method, what you call this process?
No. Recursion is when you keep calling the same function over and over again (building a stack of consecutive function calls), with a different state, until you get to a base case.
Yes it can be, because actually you are solving this by doing the same thing twice but for smaller range and you can limit the number of the recursion calls by counter, here is code for it by Swift:
func validPalindrome(_ s: String) -> Bool {
var low = 0
var high = s.count-1
return validPalindrome(s, low, high, 0)
}
func validPalindrome(_ s: String, _ low: Int, _ high: Int, _ count: Int) -> Bool {
if count > 1 {
return false
}
let sChars = Array(s)
var low = low
var high = high
while low < high {
if sChars[low] == sChars[high] {
low += 1
high -= 1
} else {
return validPalindrome(s, low+1, high, count+1) || validPalindrome(s, low, high-1, count+1)
}
}
return true
}
Hey Kevin...just FYI, this question's moved to hard category now.
really? That's weird...I just checked again and it still says easy for me
Kevin Naughton Jr. interestingly the question page shows it as easy... but if you search for it in search bar on home page, by typing 680...it says hard as difficulty level...😊
For the second func chars are not compared for initial input vals i,j but are incremented right away...why is that still working I wonder.
P.S awesome videos
That's how post increment expressions work, they actually change the values *after* the values are being read.
For better understanding try to solve this little puzzle: let i = 3; i++ - i - ++i = ? (you may execute this expression manually from left to right and check yourself in a browser's console after). Enjoy! :-)
Hey Kevin, Please upload the video for longest palindrom substring Leetcode and word search II Leetcode. Can you please do it by tomorrow? Also, word search II using Trie.
String problems are trash