MAXIMUM SWAP | LEETCODE 670 | PYTHON SOLUTION

Today we are solving a god awful problem: Maximum Swap. It's a question that is pretty easy to grasp in terms of the intuition of the problem but it's such a chore to actually code up. There's so many annoying nuances in this problem that just add up and give you a headache.

TIMESTAMPS

00:00 Intro
00:20 Question Prompt
00:28 Basic Example
01:38 Solution Intuition
02:57 Coding
12:30 Time/Space Complexity
13:55 Outro

[lordeagle]

As always, great vid! I just did the problem a few times to figure out how to make it less annoying to code up without screwing up the time/spacing complexity and here's what I came up with (which at least works in JavaScript):
1. Turn the input integer into an array of *characters* and then a plain split. So for python something like `num_as_arr = list(str(num))`that turns 6 init lines into 1 without impacting readability
2. You don't need to use integers: comparing ASCII characters/strings (because they are of exactly 1 character) will work just as well. So you can perform the swap with chars
3. Only change is at the end to remember to parse each char back to an int (via `num = num * 10 + ord(cur) - ord('0'))

This shaves off almost half the "basic" code without, IMO, affecting readability much.

[syafzal]

Super annoying question like you said! Thanks for explaining the algorithm behind it!

[rd_iimpact]

38. Count and Say is another one I hate.

[labixiaoxin]

Thanks for saying this question is a pain in the ass, I feel exactly the same.

[adityakulkarni]

Makes more sense to me like this:

if num <= 11:
return num

#convert to list, record max value index at each index from the right
nums = list(str(num))
right_max = [0] * len(nums)
cur_max = -1
cur_max_index = -1
for i in range(len(nums)-1, -1, -1):
if int(nums[i]) > cur_max:
cur_max = int(nums[i])
cur_max_index = i

right_max[i] = cur_max_index


#find where we dont replace the number with itself or the equal value. this is our swap
for i in range(len(nums)):
if right_max[i] != i and nums[i] != nums[right_max[i]]:
nums[i], nums[right_max[i]] = str(nums[right_max[i]]), str(nums[i])
break

return int(''.join(nums))

[manoelramon]

there is an easier way:
1) move from left to right until you find an value increase.. save this index
2) from the index on (1) continue scanning from left to right and find the max and its index
3) from right to left, find the first lowest number comparing to max
you will have the number.

[weeno]

I actually like this question, it reminds me of buildings w an ocean view

[mageshmcc]

Here is one of the simplest solution :))
class Solution:
def maximumSwap(self, num: int) -> int:
num_list = [int(i) for i in str(num)]
max_iter = len(num_list) - 1

num_dict = {}
for i, x in enumerate(num_list):
if x not in num_dict:
num_dict[x] = [i]
else:
num_dict[x].append(i)

i = 0
while i < max_iter:
tmp_list = num_list[i::]
small = min(tmp_list)
big = max(tmp_list)
if num_list[i] == big:
pass
else:
ith_elm = num_list[i]
num_list[i] = big
num_list[num_dict[big][-1]] = ith_elm
break
i += 1

output_num = 0
digit_place = 10**max_iter
for i in num_list:
output_num += digit_place * i
digit_place //= 10

return output_num

[kadimisettyavinash]

This problem and the next permutation problem - never liked them

[APudgyPanda]

As a java user this solution is not it

[marmikpatel]

guys, I think he dislikes this question 😂

[ManoelRamon-cs]

if num <= 11:
return num

s = list(str(num))
n = len(s)

for i in range(n-1): # find index where s[i] < s[i+1], meaning a chance to flip
if s[i] < s[i+1]:
break
else:
return num # if nothing find there is nothing to flip, return num

max_idx, max_val = -1, '!' # keep going right, find the maximum value index
for j in range(i+1, n):
if max_val <= s[j]:
max_idx, max_val = j, s[j] #found a bigger value to updte

left_idx = i # i now where max is, let's find the min. Going right to left from i, find most left value that is less than max_val
for j in range(i, -1, -1):
if s[j] < max_val:
left_idx = j

s[max_idx], s[left_idx] = s[left_idx], s[max_idx] # swap maximum after i and most left less than max

return int(''.join(s))