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
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
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!
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
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
Very nice explanation! Please do more videos
Patient explanation! Love your video!
Thank you for your kind words !
Thank you very much!
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?
Great explanation!
Thanks!
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?
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