Sequential Digits - Leetcode 1291 - Python

0:00 - Read the problem
0:06 - Drawing Explanation
4:35 - Coding Explanation
7:06 - Drawing Explanation
12:43 - Coding Explanation

leetcode 1291

#neetcode #leetcode #python

[theGameThrough]

Why do continue, when we can directly break out of the loop? like when n > high, we know for sure we are not gonna get our next answers

[mapledanish]

I defined a string “123456789” and then extracted all substrings from low.length to high.length. It made for really readable code imo, sort of a sliding window.

[imamnurbaniyusuf]

Initially, I took a different approach to solve this:
- creating a list of numbers from 1-9
- iterate through the valid sliding window
- for each of this iteration, iterate through the list of numbers, then construct the number based on the length of the current sliding window
- then check if it is within the valid ranges, if yes then append to res

Nice to see an alternative solution using queue! and Thanks for the videos!

[Vancha]

Looking at this, I'm actually pretty proud of what i came up with myself :D shorter, but less efficient then these solutions. Still happy it beat like 70% in both time and space for python.
```
def sequentialDigits(self, low: int, high: int) -> List[int]:
window = "123456789"
res = []
for i in range(len(str(low)), len(str(high))+1 ):
for j in range(i, len(window)+1):
temp = int(window[j - i:j])
if temp > high:
return res
if temp >= low:
res.append(temp)
return res
```

[MikeTypes]

after so many years of practice, i was able to come up with the queue solution similar to yours in 5mins.
#blessed

[deepfriedtoaster]

Isnt the "sorted" requirement for the result kind of trivial since the result can't have more than 36 or so elements in it? So even if you use a O(nlogn) sort on it, it should still be contstant

[samuelgunter]

for this problem, id make a lookup array (length 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36, which is a small amount of memory) of a sorted version of each increasing number and essentially perform a filter on it. you could binary search for the beginning number (no need to binary search for the end, since you can just do the comparison in the already linear copy), but I think it might not even be worth the overhead to find a binary search for the left side

[gmh]

I took a way different approach. I iterate over the string (e.g. '1234') and add +1 to each digit, and repeat until all numbers have been populated. (start from low, e.g. 1000 -> 1234 -> 2345 -> ... until greater than high). Still gets very good time and memory (same as yours almost).


def sequentialDigits(self, low: int, high: int) -> List[int]:
# My MONKEY BRAIN optimal solution (not bruteforce!)
# And it works!

res = []
str_low = str(low)
idx = 0

while True:
continue_flag = False
if idx == 0:
temp = str_low[0] # don't modify first digit when while is running for first time
else:
temp = str(int(str_low[0])+1)

for i in range(1, len(str_low)):
if temp[i-1] != '9':
temp += str(int(temp[i-1])+1)
else:
continue_flag = True
break

if continue_flag: # we come here when we have gone over, e.g. after 6789
temp = '1' + '0'*len(str_low)
idx = 0 # set to 0 so we can keep first digit fixed after addition of a 0
str_low = temp
if int(str_low) > high:
return res
continue

str_low = temp
if int(str_low) > high:
return res
if int(str_low) >= low:
res.append(int(str_low))
idx+=1

[DeathSugar]

every number of w digits differs from previous by w ones.
so my solution was to start with 12 as minimal base case, rise it until it greater or equal low bound and start adding ones for each width less or equal of hi.
code is kinda ugly, but it's pretty much constant time overall.

[triputrafauzanhradji]

Wouldn't the second solution be O(n) (if not more than O(n) of the first solution) because the while loop roughly always goes from 1 to high? I'm a little confused here.

[nicolasguillenc]

I used the string "123456789" and created substrings of it and it works but it takes too long so leetcode says "exceed time execution" :') I will have to watch this video again to get it

[CS_nb]

sliding window was my favourite solution

[nikhil]

Time complexity is log (hi-lo) base 10

[mylkrenebjorson]

welp i just type all the possibilities to collection array and iterate the array if that fit the range.
Simple, dumb, but fast and straightforward.

[deadlyecho]

I don't think a queue is necessary, only for making it a bit clean, but nice approach 👍

[razataggarwal]

Mine took 0 ms in Java. For sliding window