Recursion Interview Question - "Kth Symbol in Grammar" (Data Structures & Algorithms)

0:12 - Problem description
1:02 - Problem examples
1:37 - Algorithm Explanation
4:24 - Pseudocode (explains idea behind algorithm)
5:55 - Full code solution (explains idea behind implementation)
7:04 - Time + Space Complexity
Here's the explanation on how to solve popular Data Structure & Algorithms question on Leetcode, "Kth Symbol in Grammar". This is a classic question that we get from technical interviews at Google, Facebook, Amazon, Microsoft, and so on. Let’s try this question to learn more about the basic concept of recursion.
Please like and subscribe! Comment any of your questions / feedback down below. 😃
#interview #data_structures # algorithm #algorithms #recursion #job #google #amazon #facebook #faang #data_structures #recursive #leetcode
Facebook: / potatocoders
Linkedin: / potato-coders

[@chithyFly]

Great explaination with beautiful graph!!! Love it with your DSA explaination.

[@rustam-z]

There must be k//2 in self.kthGrammar(n-1, k/2 + k%2)

[@priyankareddy7408]

So well explained. Thanks!

[@wesammustafa9004]

Excellent Explanation, Thank you

[@surajbaranwal56.]

Great explain, helpful visuals. Thnaks

[@CyberMew]

this helped me understand easily with the recurrence relation, thanks. amazing how it will just work itself out eventually..

[@eriklee1131]

great solution!

[@sohilyadav03]

Nice Explanation

[@harshit-jain.]

Really great explanation. Couldn't understand it earlier but now got it. Thank you.

[@venkataraman7962]

simple and clear, thank you

[@bhavishahadiyal7836]

Best explanation please please keep it up

[@baro-kv8he]

I like your wording, concise. I do like and subscribe.

[@ravikumarpilla4680]

Please make more videos on DS and Algorithms. Great explanation and visuals. Loved it

[@potatocoders2028]

Thanks, will definitely do once we find the available time!

[@santoshrathod9868]

It seemed impossible before your video, but not now. Thank you so much.

[@dollyakshaya7535]

really kool I have same approach in mind but wasn't able to solve thanks for the video

[@computerlearningbyargusaca5217]

🙏🙏Very nice . love to see more 👍👍videos . 😍😍 thanks for uploading👌👌

[@potatocoders2028]

Most welcome 😊

[@tangwu3924]

Best explanation in this question

[@gunahawk6893]

dood this is amazing please do more videos man , like dp problems

[@mayankgupta7988]

I do not know why anyone has disliked it. It is a great solution.

[@snehasishroy39]

Great way of visualizing the problem as a tree

[@potatocoders2028]

Thank you! 😀 We are happy that you like the video

[@lostgoat]

This is O(n) time complexity the modulo is a constant operation, also since were only modding 2 here we can just check the first bit in k to see if its a 1 or 0

[@lokesh3526]

Bit late but...i watched many videos but ur explanation is the best 🤘

[@ibrahimk6729]

kudos!!

[@hackzyoboy2459]

Wow, loved this visualization. I solved it using another method, but this method of yours is good too!!

[@potatocoders2028]

Thanks for the feedback! ☺️ There are many ways to solve this problem, but we thought this method will be instructive of the recursion algorithm

[@jeevaalok1467]

@@potatocoders2028 may ik why k%2 operation takes O(log k) time complexity ?
& what if i use (k+1)/2 instead of " k/2 + k%2 " , inorder to figure out the ceil of k/2 . so that we reduce the complexity from O(n * log K ) to O (n * 1 ) . correct me if I am wrong ?
appreciate your help :)

[@12345ms]

Why do we need to take ceil for k/2 i.e. k/2+k%2? Why just k/2 does not work, can someone explain, please? Thank you.

[@sauravnegi8858]

is there any other way to do it?

[@sawankumar6355]

this solution is more understandble

[@amrutaparab4939]

That was so easy i spent an hour on this😭😭😭

[@saunaknandi1814]

It wasasked in which company interview??

[@day35ofdebuggingthesamelin56]

Leetcode questions like these are just questions that may show up in your coding interview

[@vietjs-music]

I thought the time complexity will be O(n)? Cause the modulo operation only takes O(1) time right.

[@potatocoders2028]

Hi Viet! Thank you for your comment. The modulo operation performs a long division, which takes a number of steps on the order of the number of digits. The number of digits of a number K scales as log(K), so the modulo operation has a time complexity of O(log K).

[@vietjs-music]

@@potatocoders2028 Thanks for the detailed explanation

[@potatocoders2028]

No problem :)

[@michael1]

@@potatocoders2028 for odd/even you can just do k&1 and in fact it's parent xnor k&1, which is 1-(parent ^ (k&1) and that's O(1). for the recursive call you can just do (k+1) // 2 no need for % at all.

[@SahilJSawant]

But why are you doing log K I think for every level you are just doing one operation so the time complexity is just O(N)

[@ben94_]

this is my question too. It looks like the operations are constant for each level?

[@roberto-rodriguez]

Accepted solution in Java:
class Solution {
public int kthGrammar(int n, int k) {
n -= 1;
k -= 1;

if(n == 0){
return 0;
}

return process(n, k);
}

public int process(int n, int k) {
if(n == 1){
return k % 2 == 0 ? 0 : 1;
}

Double two_pow_n = Math.pow(2, n);
int half = two_pow_n.intValue() / 2;

if(k < half){
return process(n - 1, k);
}else{
return invert( process(n - 1, k - half) );
}

}

public int invert(int i){
return i == 0 ? 1 : 0;
}

}