if a digit in intmap is not enough, we have to be sure the digit is greater than the current item and also we need to be sure that the index of the digit is greater than the index of the current item also
nice video! An approach I went with was keeping track of the max value right of any index and the index that max value set at. This way we can then loop left to right and if we need to swap, do it. temp = list(str(num)) right_max = temp[len(temp)-1] digit_map = {right_max: len(temp)-1} num_max = len(temp) *[right_max] ## Build array for i in range(len(temp)-2,-1,-1): if temp[i] > right_max: num_max[i], right_max = temp[i], temp[i] digit_map[right_max] = i if num_max[i] < right_max: num_max[i] = right_max for i in range(len(temp)-1): if temp[i] < num_max[i]: index = digit_map[ num_max[i] ] temp[i], temp[index] = temp[index], temp[i] return int( ''.join(temp)) return num
Thank you for the video as well. Also wondering what the time complexity is for the second approach? Are time and space complexity both O(N), where N is number of elements in the num?
if a digit in intmap is not enough, we have to be sure the digit is greater than the current item and also we need to be sure that the index of the digit is greater than the index of the current item also
Awesome, for a very long time I struggled to find a better solution than brute force for this problem! This is it!
if a digit in intmap is not enough, we have to be sure the digit is greater than the current item and also we need to be sure that the index of the digit is greater than the index of the current item also
nice video!
An approach I went with was keeping track of the max value right of any index and the index that max value set at.
This way we can then loop left to right and if we need to swap, do it.
temp = list(str(num))
right_max = temp[len(temp)-1]
digit_map = {right_max: len(temp)-1}
num_max = len(temp) *[right_max]
## Build array
for i in range(len(temp)-2,-1,-1):
if temp[i] > right_max:
num_max[i], right_max = temp[i], temp[i]
digit_map[right_max] = i
if num_max[i] < right_max:
num_max[i] = right_max
for i in range(len(temp)-1):
if temp[i] < num_max[i]:
index = digit_map[ num_max[i] ]
temp[i], temp[index] = temp[index], temp[i]
return int( ''.join(temp))
return num
I did not understand the swapping part. Why do we say numstr[digit]? From the example, would it not be numstr[7] when we check if 7 is in the intMap?
For the input case A=7599 and B=2, it will return 9957 but the answer should be 9975
very clear and detailed explain!!! Thanks! Could you please also talk about time complexity?
Thank you for your kind words Jingjing
Thank you for the video as well. Also wondering what the time complexity is for the second approach? Are time and space complexity both O(N), where N is number of elements in the num?
Very nice explanation! Please do more videos
Patient explanation! Love your video!
Thank you for your kind words !
Thank you very much!
Great explanation!
Thanks!
thank you!!!
excellent
Thank you for your kind words lil zjay.
if a digit in intmap is not enough, we have to be sure the digit is greater than the current item and also we need to be sure that the index of the digit is greater than the index of the current item also