Maximum Swaps - Leetcode 670 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
11:24 - Coding Explanation

leetcode 670

#neetcode #leetcode #python

[gavinebenezer]

Beats 69.69% of users in runtime is diabolical

[as-zg]

"tell me why?" this cant be swapped ---was very needed sir

[anthonyhsu]

I appreciated the real-time thinking process. I was aware of the problems with the first two approaches, and I’m glad I can think more thoroughly now after some practice

[Anubhab-bb]

Solution might help ; the 2 pass one :-

public int maximumSwap(int num) {
int maxn = num;
String s = Integer.toString(num);
int n = s.length();
int [] arr = new int[n];
int maxi = n-1;
for(int i = n-1;i>=0;i--){
if(s.charAt(i) > s.charAt(maxi)){
maxi = i;
}
arr[i] = maxi;
}
for (int j = 0; j < n; j++) {
if (s.charAt(j) != s.charAt(arr[j])) {
char[] chArr = s.toCharArray();
// now easily we can swap char and then check
char temp = chArr[j];
chArr[j] = chArr[arr[j]];
chArr[arr[j]] = temp;
int swappedNum = Integer.parseInt(new String(chArr));
return swappedNum;
}
}
return num;

[suryateja_]

Leetcode sometimes goes NUTS... I submitted an O(n^2) code and it beats 100% of users.

[mcw]

just fyi. swap_i and swap_j will be both -1 if the numbers are in non-increasing order (e.g. 9937). swapping these indexes at the end will not cause an error in python because we would be just swapping with itself on the final index. but you will need to check for the negative indexes on other programming languages

[devdanlight]

Could use this, might be more intuitive for some:

class Solution:
def maximumSwap(self, num: int) -> int:
# Convert the number to a list of characters for easy manipulation
num_list = list(str(num))

# Track the last occurrence of each digit (0-9)
last = {int(d): i for i, d in enumerate(num_list)}

# Traverse the number from left to right
for i, digit in enumerate(num_list):
# Check for a larger digit to swap
for d in range(9, int(digit), -1):
if last.get(d, -1) > i:
# Swap and return the new number
num_list[i], num_list[last[d]] = num_list[last[d]], num_list[i]
return int(''.join(num_list))

# If no swap occurred, return the original number
return num

[chaitanyayeole]

Leetcode is crazy, it passed my O(n^2) solution which beats 96.08%🤣🤣🤣

[williamglane]

Try using a dictionary of digit to last seen position, i.e. {int(ch) : i for i, ch in enumerate(s)}, where s = str(nums).

[ayushanand]

this isn't the most optimal solution, , we can still obtain a constant space linear time solution as against this linear space solution

[kckrishna]

why do I feel the two pass solution is still an issue? Correct me if I am wrong, just by changing the value would not help as you need to swap. In your example 5435 the result would be 5535 instead it should be 5534. You are not storing index of the current max.

[bandarupawankumar]

I tried the 2 pass approach after watching this n leetcode gave beats 100% of users, to it

[ashleywilkonson]

Technically all the solutions you had would be constant time due to the input being an integer.

[lost-wind]

Thank you, everytime I see one of this, I get so excited. ;)

[wilmahutson-ew]

I love all of your videos. You've helped me so much in my life. But I must say this has to be one of the most frustrating videos ever to watch. We go down a path for minutes at a time only to say actually thats not the way we want to do it. Like you definitely couldve included the swap_j part in the initial presentation of the approach.

So tough but it still does make sense. thanks so much for the video.

[Ahmad-hzv]

was gonna use a heap for some reason spent 30 mins tryna implement it but then got it. thank you

[shibambiswas]

Just changed if-if to if-elif and got 100% in runtime performance.

[RK-cd]

it is crazy I had 100.00% tc.... LC is funny

[aps]

Just curious -- how did you know the problem of the day so quickly?

[AlthafNazeer-nm]

My solution :)

class Solution:
def maximumSwap(self, num: int) -> int:
if str(num) == sorted(str(num)) or num < 10:
return num
items = [i for i in str(num)]
new_items = sorted(items)[::-1]
i = 0
while i < len(items):
if new_items [i] != items[i]:
val = items[i]
req = max(items[i : ])
for j in range(len(items) - 1, i, -1 ):
if items[j] == req:
idx = j
break
items[i], items[idx] = items[idx], items[i]
break
else:
i += 1

return int("".join(items))