Lexicographical Numbers | Simple DFS | Leetcode 386 | codestorywithMIK

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

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

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

[AmandeepSingh-uqwp]

I also wrote the same code but still comes here to expand my knowledge from mik sir.

[AdarshSingh-cdqt]

Bhaii bht accha explain kiya aapne thanks

[Playvish]

watched the video till 6:40 and solved the question successfully

[gui-codes]

aaj wala easy tha bhaiya. kuch mistakes karne k baad I was able to solve.

[best]

Another approach (using comparator)

class Solution {
public:
vector<int> lexicalOrder(int n) {
auto lambda = [&](int &a, int &b)
{
string n1 = to_string(a);
string n2 = to_string(b);
return n2 > n1 ;
};
vector<int> nums;
for(int i=1 ; i<=n ; i++)
{
nums.push_back(i);
}
sort(begin(nums), end(nums), lambda);
return nums;
}
};

[vikramramkumar]

Hey! Could you make a playlist for Fenwick Trees??

[rev_krakken]

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.

[gui-codes]

Bhaiya please post today's POTD - Leetcode - 440 - K-th Smallest in Lexicographical Order

[shivanshplays]

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<int>& arr) {
if (no > n)
return;

for (int i = no; i < no + 10 && i <= n; i++) {
if (i != 0) {
arr.push_back(i);
if (i * 10 <= n) {
recur(i * 10, n, arr);
}
}
}

return;
}
vector<int> lexicalOrder(int n) {
vector<int> arr;
recur(0, n, arr);
return arr;
}
};


ps: it took me 2 hours to come up with this approach :, )

[harshitgupta]

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]<s2[i];
}

class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> ans(n);
for(int i=1;i<=n;i++){
ans[i-1] = i;
}
sort(ans.begin(), ans.end(), cmp);
return ans;
}
};

[dayashankarlakhotia]

public int lexicalOrder(int n){
List<Integer>ans=new ArrayList<>();
int cur=1;
while(ans.size()<n){
ans.add(cur);
if(cur*10<=n){
cur*=10;
}else{
while(cur%10==9||cur==n){
cur/=10;
}
cur++;
}
}
return ans;
this is iterator version.
Tc=0(n);
Sc=0(1);

[abhishek_]

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?

[manasdeora]

tried implementing same solution in java, gives TLE.


public class Solution {
public List<Integer> lexicalOrder(int n) {

List<Integer> ans = new ArrayList<>();

for (int i = 1; i <= n; i++) {

solve(i, n, ans);
}
return ans;

}

private static void solve(int i, int n, List<Integer> ans) {

if (i > n) {
return;
}

if(ans.contains(i)) {
return;
}
ans.add(i);

for (int j = 0; j <= 9; j++) {

int x = (i * 10) + j;
if(x>n){
return;
}
solve(x, n, ans);
}
}
}

[AkOp-bfvm]

I TRIED SOMETHING WEIRD INITIALLY 😂😂😂😂😂😂😂😂. THIS IS THE EXAMPLE HOW NOT TO WRITE THE CODE USING CUSTOM COMPARATOR
class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> result;

for(int i=1;i<=n;i++){
result.push_back(i);
}

auto lambda= [](int a, int b){
string a1= to_string(a);
string b1= to_string(b);

return a1<b1;
};

sort(result.begin(), result.end(), lambda);
return result;
}
};

[AlexKumarI-cd]

bhaiya make a video on meet in the middle algorithm

[yashwardhansingh]

sir how can we done this with O(1) space

[sujayvikramgs]

bhai aaj ka problem meh tho same method se solve liya tho TLE aagya
time efficient nhi haina then why this T_T;

[kancharlasrimannarayana]

can we solve it in O(1) space conplexity?

[aizadiqbal]

brute force hi kar diya tha, extra space use karke :D and sorting pe, somehow it passed...

class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>();
List<String> list = new ArrayList<>();
for(int i=1; i<=n; i++){

}
Collections.sort(list);
for(String str : list){
int x = Integer.parseInt(str);
ans.add(x);
}
return ans;
}
}