Lexicographical Numbers - Leetcode 386 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
4:56 - Coding Explanation
7:08 - Optimized Explanation
10:23 - Optimized Solution

leetcode 386

#neetcode #leetcode #python

[Wasabi.Script]

questions like these occasionally have me questioning whether i'm reallly cutout for comp sci. cus in no universe can i get to a point where i can solve them myself ....anyways good vid

[AdityaSingh-thxu]

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

[floman]

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

[Gojo-hliu]

Thank you sooo much for your daily uploads

[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,

[souriksharma]

I tried doing it with string for simplicity 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.

[MP-nyep]

Great explanation as always. Thank you !

[albin_joby]

res = []
def check(num):
for i in range(0, 10):
val = num*10+i
if val <= n:
res.append(val)
check(val)
else:
return

for num in range(1, n+1):
if num <= n and num not in res:
res.append(num)
check(num)

return res

[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😅

[skyjoe]

hum, I couldn't understand the 2nd approach.

[cupidchakma]

Is the time complexity of this is O(n)^2?

[abdalmlck]

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

[tauicsicsics]

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

[nitishyadav]

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 ?

[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.

[austinmclaughlin]

You're the modern day Gayle Laakmann McDowell