Lexicographical Numbers | Simple DFS | Leetcode 386 | codestorywithMIK
HTML-код
- Опубликовано: 10 окт 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 6th Video of our Playlist "Recursion : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a simple DFS problem : Lexicographical Numbers | Simple DFS | Leetcode 386 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Lexicographical Numbers | Simple DFS | Leetcode 386 | codestorywithMIK
Company Tags : will update later
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
The approach used above is based on a Depth-First Search (DFS) to generate numbers in lexicographical order. Here's a summary:
Recursive DFS Traversal: The solve method explores all possible numbers that can be formed by appending digits (0-9) to the current number. It starts with numbers from 1 to 9 (as lexicographical order starts from 1) and recursively generates subsequent numbers by multiplying the current number by 10 and adding a digit.
Termination Condition: The recursion stops when the next number exceeds the given limit n.
Efficiency: By generating the next number in a controlled manner (starting with 1-9, then 10-99, etc.), the algorithm avoids sorting, as it directly produces numbers in lexicographical order.
Result Storage: The valid numbers are stored in a List as they are generated and returned as the final result.
This approach efficiently constructs the lexicographical sequence of numbers without sorting, using DFS to ensure all possible numbers are explored in the correct order.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik
I also wrote the same code but still comes here to expand my knowledge from mik sir.
watched the video till 6:40 and solved the question successfully
exactly....
Already done. Here to support 😊
Same
Haddi ur leetcode I'd??
Bhaii bht accha explain kiya aapne thanks
Thank you so much Bhaiya ji 🙏🙏🙏
very good explanation
aaj wala easy tha bhaiya. kuch mistakes karne k baad I was able to solve.
Hey! Could you make a playlist for Fenwick Trees??
Another approach (using comparator)
class Solution {
public:
vector lexicalOrder(int n) {
auto lambda = [&](int &a , int &b)
{
string n1 = to_string(a);
string n2 = to_string(b);
return n2 > n1 ;
};
vector nums;
for(int i=1 ; i
Even I did the same way but this takes nlogn TC. The approach suggested in the video is actually better
Sorting nlogn lega
I tried 4 approaches
1. First used basic sorting based on string comparison
2. Next approach I used tries to implement dfs
3. 3rd one I found out that trie is not required and used bfs
4. 4th one I used iteratively.
can you share the code of 3rd and 4th approach
thanks
thank you!!
Bhaiya please post today's POTD - Leetcode - 440 - K-th Smallest in Lexicographical Order
Thank you bhaiyya
Another approach using comparator function
bool cmp(int a,int b){
string s1 = to_string(a);
string s2 = to_string(b);
int i = 0;
while(s1[i]==s2[i]){
i++;
}
return s1[i]
I did this as well
thanks for sharing this approach🙏
@@rockykumarverma980 😇🙌
This would lead to TLE since string comparision would take O(max(a,b)) for worst case
@@Its_Shubham_Negi no u can copy this code it's running fine and string length would be 5 at max as limit of n is 10^4 so it will take O(5) in worst case eventually O(1)
Hello MIK sir, here is the approach that I came up with, I think that this also takes the same time and space complexity, although could you please confirm? TC:O(n) SC:O(log10(n))
class Solution {
public:
void recur(int no, int n, vector& arr) {
if (no > n)
return;
for (int i = no; i < no + 10 && i
public int lexicalOrder(int n){
Listans=new ArrayList();
int cur=1;
while(ans.size()
Aaj wali video kis playlist mei hai ek playlist concept of recursion krke apne daali hai usme 18 videos hai usse alag bhi koi recursion playlist hai apke channel ki?
Here is the list -
I usually create two playlists for every topic :
1) Concepts Playlist - Contains from basic concepts to expert concepts.
2) Popular Interview Problems playlist.
I have created concepts and interview problems playlist for
1) Graph
2) Recursion
3) DP
4) Segment Tree
Planning soon to create concepts playlist for Tree as well.
Graph Concepts - ruclips.net/p/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY&si=lZG2IJTmSW4kRrx-
Graph Popular Interview Problems - ruclips.net/p/PLpIkg8OmuX-I_49pdy1XFY6OcATnxUrrO&si=CG2JvGWVmvoSqvWA
Recursion Concepts - ruclips.net/p/PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM&si=614iI4NyHY-FTeJH
Recursion Problems (In progress) - ruclips.net/p/PLpIkg8OmuX-IXOgDP_YYiJFqfCFKFBDkO&si=88fBhRnr62OYTnDP
DP Concepts (In progress) - ruclips.net/p/PLpIkg8OmuX-JhFpkhgrAwZRtukO0SkwAt&si=laFVYy6ep2BkOg0s
DP Popular interview problems - ruclips.net/p/PLpIkg8OmuX-L_QqcKB5abYynQbonaNcq3&si=VHEn9b-wqTnAVyyi
Segment Tree Concepts -
ruclips.net/p/PLpIkg8OmuX-K1qUIQToCllUO0UIKXt8dB&si=xm7DqRN4H0eZwna4
@@codestorywithMIK thank you so much bhaiya
bhaiya make a video on meet in the middle algorithm
ye kya hai bhai ?
what about iterative?
sir how can we done this with O(1) space
space agar dekha jae to O(1) hi hai.
Editorial me dekho leetcode k - Given that the maximum value for n is 50,000, the maximum number of digits d is 5. Thus, the recursion stack depth and corresponding space complexity is O(d), which simplifies to O(log
10
(n)), but with a maximum constant value of 5 for practical constraints. It can also be argued as O(1).
from where did you learn dsa?
tried implementing same solution in java, gives TLE.
public class Solution {
public List lexicalOrder(int n) {
List ans = new ArrayList();
for (int i = 1; i n) {
return;
}
if(ans.contains(i)) {
return;
}
ans.add(i);
for (int j = 0; j n){
return;
}
solve(x, n, ans);
}
}
}
if(ans.contains(i)) {
return;
} ❌❌
why this extra check?
it takes O(ans.length()) each time
*****************************************
for (int i = 1; i
same code in java giving TLE.
Ist🎉❤
can we solve it in O(1) space conplexity?
space agar dekha jae to O(1) hi hai.
Editorial me dekho leetcode k - Given that the maximum value for n is 50,000, the maximum number of digits d is 5. Thus, the recursion stack depth and corresponding space complexity is O(d), which simplifies to O(log
10
(n)), but with a maximum constant value of 5 for practical constraints. It can also be argued as O(1).
thank you but if the constraint changes means?
and if we change the question like this if we given a random array of numbers as input and asked to sort lexxigraphicak means how to do it?
@@kancharlasrimannarayana7068 I don't quite understand what you mean but if you are saying the array has random elements and you want to sort in lexicographical order, that is nothing but the usual ascending/increasing order sorting. Lexicographically usually means according to dictionary, so yeah 1 then 2 then 3 then 4 and so on. That is just normal sorting
@@brokegod5871,
[1,10,3,5,22] as input
normal sort output is [1,3,5,10,22]
but lexicographical sort output is [1,10,22,3,5]
@@brokegod5871 right
I TRIED SOMETHING WEIRD INITIALLY 😂😂😂😂😂😂😂😂. THIS IS THE EXAMPLE HOW NOT TO WRITE THE CODE USING CUSTOM COMPARATOR
class Solution {
public:
vector lexicalOrder(int n) {
vector result;
for(int i=1;i
I thought the same😂😂
bhai aaj ka problem meh tho same method se solve liya tho TLE aagya
time efficient nhi haina then why this T_T;
Yes if you use array to store it will give - MLE
and if you solve without using array, it will give TLE because constraint is huge.
We need logarithmic approach.
The video is being uploaded now ❤️🙏
@@codestorywithMIK thanks bhaiya
will watch the video now. thanks for all your efforts bhaiya :)
didnt understand the space complexity
For recursion problems, we always check what is the maximum depth of the recursion tree.
If you notice , for any recursion call, you won’t go more than digits deep in recursion.
Please also refer to my Recursion Concepts playlist where I have explained how to calculate space complexity of recursion calls
@@codestorywithMIK bhaiya i understand the recursion tree but why it is log base 10?
Because for any decimal number , the number of digits can be calculated by log(number) to the base 10.
Let’s understand from an example :
number = 234
To find the number of digits, keep dividing it by 10z
234/10 =23
23/10 =2
2/10 =0
If you notice how many times you had to divide 243 by 10 ?
3
Dividing by 10 until the number is 0 i.e. log10(number)
@@codestorywithMIK thanks bhaiya now i understood
brute force hi kar diya tha, extra space use karke :D and sorting pe, somehow it passed...
class Solution {
public List lexicalOrder(int n) {
List ans = new ArrayList();
List list = new ArrayList();
for(int i=1; i