Correct. Given that the order of elements in the queue are always in increasing order (same reason the output is sorted), as soon as we find an n > high, we can break. Somehow I didn't catch that, my mistake. Thanks for pointing it out.
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!
ans = [] digits = '123456789' length_low, length_high = len(str(low)), len(str(high)) for length in range(length_low, length_high + 1): for i in range(10 - length): if low
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.
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 ```
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
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.
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
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
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
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.
I just had an Meta screening interview, and even though I got both answers right, I didn't take care of some edge cases in the second one, until the interviewer pointed it out. I could have done it, but there was just so much anxiety about not having enough time or being judged by someone that I just could barely form a sentence. I 100% could have solved that if I wasn't under pressure, but I have no one else to blame but myself. I studied for a whole month, 8pm to 4 or 5am. and just a simple binary tree problem got to me. I'm so disappointed at myself
It happens, I did a blunder at my Huawei interview. The interviewer asked me an array question that I tried solving with Hash map. It was supposed to be solved by recursion. I could have instantly came up with a solution if only I thought about recursion. Anyways, the fact is it is okay. I'm sure you learned something from it and I'm sure you will get another chance. Good luck with your job hunt.!
@@Abhaysharma-jx1qv hey thanks for that. I always prayed that I get a recursion and I ended up screwing that. but yeah, it was anxiety and pressure of finishing it on time. I'll try to manage those next time. I hope you are successful too
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
Agree, if "break" out of the loop, it would be more efficient.
Correct. Given that the order of elements in the queue are always in increasing order (same reason the output is sorted), as soon as we find an n > high, we can break.
Somehow I didn't catch that, my mistake. Thanks for pointing it out.
simply if n>high return ans;
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!
damn! nice approach brother
ans = []
digits = '123456789'
length_low, length_high = len(str(low)), len(str(high))
for length in range(length_low, length_high + 1):
for i in range(10 - length):
if low
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.
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
```
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
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.
after so many years of practice, i was able to come up with the queue solution similar to yours in 5mins.
#blessed
can you tell me how many years of practise and how many problems have you solved on leetcode.....I want to become that intuitive as well
@@devkirandass7930 unfortunately...8, im not smart
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
Sort to avoid complexity of having a set to prevent duplicates
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
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
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.
Time complexity is log (hi-lo) base 10
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.
I don't think a queue is necessary, only for making it a bit clean, but nice approach 👍
sliding window was my favourite solution
Thank you so much
I love you.
palindrome concept and sliding window
I couldn't code this one 😿
Mine took 0 ms in Java. For sliding window
Is measurement for java programs broken? I've also had a couple 0ms solutions :S makes no sense to me
Notice , the time is in integer , so I believe it got roundoff or truncated.
Python runtime is slow so I think it makes sense.
@@razataggarwal7365 right that makes sense
First
I just had an Meta screening interview, and even though I got both answers right, I didn't take care of some edge cases in the second one, until the interviewer pointed it out.
I could have done it, but there was just so much anxiety about not having enough time or being judged by someone that I just could barely form a sentence.
I 100% could have solved that if I wasn't under pressure, but I have no one else to blame but myself. I studied for a whole month, 8pm to 4 or 5am. and just a simple binary tree problem got to me. I'm so disappointed at myself
@@catjamcoin palindrome with at most one character off, and check if all nodes in a binary tree is equal to the average of all children below it
It happens, I did a blunder at my Huawei interview. The interviewer asked me an array question that I tried solving with Hash map. It was supposed to be solved by recursion. I could have instantly came up with a solution if only I thought about recursion.
Anyways, the fact is it is okay. I'm sure you learned something from it and I'm sure you will get another chance. Good luck with your job hunt.!
@@Abhaysharma-jx1qv hey thanks for that. I always prayed that I get a recursion and I ended up screwing that. but yeah, it was anxiety and pressure of finishing it on time. I'll try to manage those next time. I hope you are successful too