Lexicographical Numbers - Leetcode 386 - Python

[@AdityaSingh-th7xu]

Great Explanation, Always crushed my doubts 😂, Keeping Neetcoding❤

[@phillipwils]

Excellent presentation as always.
Thanks for showing the recursive and iterative solutions.
By the way, I was reviewing the code by hand and I noticed that every
number is visited 10 times instead of once for the recursive
implementation. The time complexity is still linear.
The recursive solution time complexity is
Time: O(10*n) => 10 * O(n) => O(n)
Verify with paper and code with n = 275
def __init__(self):
self.count = 0
def dfs(start):
self.count += 1
...
print(self.count) # 2759)
return result
n=275
dfs(1) res = [1,
dfs(10) res = [1,10,
dfs(100) res = [1,10,100,
for [0..9]
dfs(100), dfs(101), ... dfs(109)
dfs(1000), dfs(1010),...dfs(1090)
dfs(101) res = [1,10,100,101,

[@Gojo-hl7iu]

Thank you sooo much for your daily uploads

[@sriramgugulothu4195]

Very clear explanation.

[@souriksharma]

I tried doing it with string for simplicity but.........yeah it exceeded the time limit and when I ran in in my IDE it took wooping 32.3 sec to sort 14959 in lexicographical order.

[@floman3158]

Something about recursive functions is annoying me so much that I always try to avoid those solutions.

[@leeroymlg4692]

you should learn it. some problems are overly complicated without recursion. like binary tree

[@MP-ny3ep]

Great explanation as always. Thank you !

[@ngoquangtrung234]

Great explaination.

[@satyamjha68]

Solved it using Trie !

[@RIPNANI]

Bro look at the follow ups

[@satyamjha68]

@@RIPNANI Ya I know that ! Its just that this approach came to my mind first!

[@deepakjain4481]

@@satyamjha68 how to solve it using that

[@RIPNANI]

@@satyamjha68 k

[@_sf_editz1870]

Just like everyday nice and smooth

[@ap2s2000]

I love you neet

[@abdalmlck4498]

but how SC is 1 ? you did save it in the res ?

[@VanjeAv]

Amazing thanks

[@jamescraft5300]

hello!

[@GullemClydeCyrilS]

awesome!

[@maanas_sehgal]

Hey I need suggestions!
So I am 1526 rated on Leetcode rn and I was planning to start with neetcode sheet. Should I pursue 150 or 580 first? I mean 580 has all the types of problems but will take long. 150 has important ones😅

[@neks2081]

dont do 580, solve 150 and then do questions by topics you suck at

[@maanas_sehgal]

@@neks2081 k

[@albin_joby]

res = []
def check(num):
for i in range(0,10):
val = num*10+i
if val

[@Sarojkumar-yh9uy]

res = []
def check(num):
for i in range(0,10):
val = num*10+i
if val

[@deepakjain4481]

i tried it but i think it does not work

[@tauicsicsics]

Can you please do Basic Calculator 1 and 2? TBH all Top Leetcode 150 interview questions would be great, thanks.

[@mcbotface]

Why do you make easy problems complicated?
lst = [i for i in range(1,n+1)]
return sorted(lst, key=lambda x:str(x))
This solution had 59ms runtime and runtime was better than 96.89% solutions.

[@NeetCodeIO]

Try to compare the time complexity of your solution with mine. Maybe you will figure it out. Maybe not.

[@mcbotface]

@@NeetCodeIO Yeah my solution has TC of O(NlogN) while yours has O(N)

[@gmh14]

@@mcbotface ????? the question states TC should be O(n)

[@mcbotface]

@@NeetCodeIO You were right.
I get "memory limit exceeded" for today's POTD using yesterday's approach
return sorted([i for i in range(1,n+1)], key=lambda x:str(x))[k-1]

[@mcbotface]

@@gmh14 No I guess. That's why my solution was accepted. Although the TC was O(NlogN)

[@100nitishyadav8]

why people using dfs in this, i just made a list from 1 to n the custom sorted it using comparator by converting into string is that bad solution ?

[@homelander.lover9114]

Constraint I O(n), sorting is n logn

[@33galactus]

@@homelander.lover9114 Exactly, your solution is simple but O(nlogn) time and O(n) space complexity make it sub-optimal.

[@mohammedsuhail.s192]

i think it was not a bad solution but the contraint should play in the problem because they want to be space complexity should be O(1) so we dont create any extra space for that it is my intuation

[@sriramgugulothu4195]

There is a constraint of running algorithm in O(n). Sorting takes more than O(n).

[@austinmclaughlin8407]

You're the modern day Gayle Laakmann McDowell