class Solution { public int maximumSwap(int num) { char[] s = Integer.toString(num).toCharArray(); //using post max array int[] max = new int[s.length]; max[s.length-1] = s.length-1; for(int i = s.length-2; i>=0; i--){ if(s[i]>s[max[i+1]]){ max[i] = i; }else{ max[i] = max[i+1]; } } for(int i=0; i
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
Summary Input Conversion: Convert the number to a list of characters for easy manipulation. Last Occurrence Tracking: Create a dictionary to track the last index of each digit. Digit Traversal: Iterate through each digit and check if a larger digit exists to the right. Swapping: If a larger digit is found, swap it with the current digit and return the new number immediately. Return Original: If no swap occurs, return the original number. Time and Space Complexity Time Complexity: The outer loop runs for each digit, and the inner loop checks digits from 9 down to the current digit. In the worst case, this leads to O(n⋅10)=O(n) where n is the number of digits in num. Space Complexity: The space used for last dictionary is O(1) because it can only contain at most 10 entries (for digits 0-9). The list num_list requires O(n) space, where n is the number of digits. Hence, the overall space complexity is O(n).
QID Question name Asked Date 349 Intersection Of Two Arrays 632 Smallest Range Covering Elements From K Lists 2024-10-13 641 Design Circular Deque 930 Binary Subarrays With Sum 962 Maximum Width Ramp 2024-10-10 1105 Filling Bookcase Shelves 1233 Remove Sub Folders From The Filesystem 1277 Count Square Submatrices With All Ones 1608 Special Array With X Elements Greater Than Or Equal X 1671 Minimum Number Of Removals To Make Mountain Array 1942 The Number Of The Smallest Unoccupied Chair 2024-10-11 2044 Count Number Of Maximum Bitwise Or Subsets 2406 Divide Intervals Into Minimum Number Of Groups 2024-10-12 2416 Sum Of Prefix Scores Of Strings 2458 Height Of Binary Tree After Subtree Removal Queries 2463 Minimum Total Distance Traveled 2530 Maximal Score After Applying K Operations 2024-10-14 2664 The Knights Tour 2742 Painting The Walls 2838 Maximum Coins Heroes Can Collect 2024-10-08 1593 Split A String Into The Max Number Of Unique Substrings 1963 Minimum Number Of Swaps To Make The String Balanced 2024-10-08 2938 Separate Black And White Balls 2024-10-15 921 Minimum Add To Make Parentheses Valid 2024-10-09 1106 Parsing A Boolean Expression 670 Maximum Swap 2024-10-17 1405 Longest Happy String 2024-10-16 2583 Kth Largest Sum In A Binary Tree 1545 Find Kth Bit In Nth Binary String 687 Longest Univalue Path 968 Binary Tree Cameras 841 Keys And Rooms Now even you know
Seems like extra work at the one pass soln. My algorithm: - set best to original number - set max to rightmost digit - iterate right to left - update max if necessary - at every element, if max> el, swap max and el and set best (greatest value) - return best after loop
I believe despite the input being an integer dose not change the fact that it was converted into string of chars and stored in num which is will take O(n) time, which later is iterated to run the swapping logic on each number on the list already counts as a linear run time along with the join at last when returning the number. Therefore, this solution has three steps which takes O(n) time complexity [O(n) + O(n) + O(n) = O(n)]. So this solution has O(n) time complexity.
@ashleywilkonson386 let's go back to basics right, so when the algorithm runs on constant time regardless of an inpute size then we can say that the algorithm has the time complexity of O(n). For eg: let's say there's a function which takes an array of integers of size 1000 but it only returns the specified index arr[12] then it's a constant time regardless of it input size upper bound which is 1000. But let's say if we're trying to find the maximum integer from the array then we need to iterate through each elements of array which means if we go by brut force we will be iterating 1000 times. So here's the difference our first problem only needs to access specifid index of array and return and latter requires to find the max integer, first solution doesn't depend on the input size but latter depends on the input size as we need to loop through the array to get to our expected output. Therefore, the solution on this video takes O(n) time to solve the problem.
class Solution { public: int maximumSwap(int num) { string numStr = to_string(num); int n = numStr.size(); vector maxRightIndex(n); // Stores the index of the max digit from // current position to the end // First pass: Populate maxRightIndex with the index of the largest // digit to the right of each position maxRightIndex[n - 1] = n - 1; for (int i = n - 2; i >= 0; --i) { maxRightIndex[i] = (numStr[i] > numStr[maxRightIndex[i + 1]]) ? i : maxRightIndex[i + 1]; } // Second pass: Find the first place where we can swap to maximize the // number for (int i = 0; i < n; ++i) { if (numStr[i] < numStr[maxRightIndex[i]]) { swap(numStr[i], numStr[maxRightIndex[i]]); // Swap to maximize the number return stoi(numStr); // Return the new number immediately after // the swap } } return num; // Return the original number if no swap can maximize it } };
why can't it be solved using the max_heap? please do help me wrote code which is passing the sample test cases and giving the correct output for text case no-77 while doing DRY RUN but giving the wrong output
class Solution: def maximumSwap(self, num: int) -> int: str_num=list(str(num)) lst=[(-int(e),i) for i,e in enumerate(str_num)] heapq.heapify(lst) swap=False i=0
while lst:
digit,indx=heapq.heappop(lst) digit=digit*-1
if int(str_num[i])==digit: i+=1
else: ind=-1 while lst and -lst[0][0]==digit: _,ind = heapq.heappop(lst) if ind != -1: indx=ind print(str_num[indx],str_num[i],i,indx) str_num[i],str_num[indx]=str_num[indx],str_num[i] break return int("".join(str_num)) help me is it OK?
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))
this is my code for two paths im passing 105/112 cases can anyone help me figure out why this isnt working please? class Solution: def maximumSwap(self, num: int) -> int: number = [int(n) for n in str(num)] print(number) max_val = 0 max_index = number.index(max(number)) max_arr = [0 for n in number] # R -> L storing max array for i in range(len(number)-1, -1, -1): if number[i] > max_val: max_val = number[i] max_index = i max_arr[i] = max_val # L -> R to check all values to the left of max_index for i in range(max_index): if number[i] < max_val: temp = number[i] number[i] = max_val number[max_index] = temp break out = "" for n in number: out += str(n) return int(out)
6:48 we can still keep the track of maxvalue post the index by updating the maxvalue right before the inner loop starts for(int j =0;jj;i--){ if(s[i]-'0' > s[maxindex]-'0') maxindex = i; } if(s[maxindex]-'0' > s[j]-'0'){ var t = s[maxindex]; s[maxindex] = s[j]; s[j] = t; break; } }
class Solution: def maximumSwap(self, num: int) -> int: s = str(num) sorted_s = ''.join(sorted(s, reverse=True)) r = list(s)
for i in range(len(sorted_s)): if sorted_s[i] != r[i]: c = sorted_s[i] d = r[i] r[i] = c for j in range(len(sorted_s) - 1, -1, -1): if c == r[j] and j != i: r[j] = d break break
This solution would work, however the bottleneck of this algorithm is the sorting on the start because it takes O(nlogn). A way to optimize this would be to change the sort to a max heap. heapq.heapify function takes O(n) time, which is faster.
@@rajGg-h3g n in this case is the digit of num. I thought about the algorithm as general as possible, that's why I said the sorting time is O(nlogn). Since the problem only have 9 digits at maximum, the time difference may not be so apparent at the end.
bro I wrote a 50 line monstrosity. with 2 helper function. and finally it worked OR SO I THOUGHT. but damn there were like 1 test cases which fuked me up fixed it then it broke some other test case best result was 110/112 . wasted 2 hours, kinda solved it but it failed. here i am EDIT - here is the monstrosity if anyone is interested Do NOT ask me what it is or how it works, coz i myself forgot what this is supposed to do. ``` class Solution { public: int firstNonDecreasingIndex(string s) { for (int i = 0; i < s.length() - 1; i++) { if (s[i] front1; i--) { if (s[i] > a) { a = s[i]; } } return a; } int maximumSwap(int num) { string intnum = to_string(num); string temp = intnum; int currgreatest = num; int front = 0, back = intnum.size()-1; char sl = greatestInt(intnum); int i = intnum.size()-1; for (int i = temp.size() - 1; i >= 0; i--) { if (temp[i] == sl) { back = i; break; } } while(front < back){ if (temp[front] < temp[back]){ swap(temp[front], temp[back]); } int test = stoi(temp); if(test > currgreatest){ currgreatest = test; } temp = intnum; front++; } return currgreatest; } }; ```
check out the monstrosity i first wrote: class Solution { public: int findRightMostGreatestChar(const string &str, int startIdx, int endIdx) { if (startIdx < 0 || endIdx >= str.length() || startIdx > endIdx) { return -1; // Invalid range } char baseChar = str[startIdx]; // Set base char as str[startIdx] int resultIdx = -1; // To store the index of the rightmost greatest char char maxChar = baseChar; // Initially set maxChar as baseChar // Traverse the substring from startIdx to endIdx (right to left) for (int i = endIdx; i > startIdx; --i) { if (str[i] > maxChar) { maxChar = str[i]; // Update maxChar to the current greatest character resultIdx = i; // Update resultIdx to the rightmost index of the greatest character } } return resultIdx; // Return the index of the rightmost greatest character } int maximumSwap(int num) { string number = to_string(num); //if digits are in descending order, no greater number is possible if( is_sorted( number.rbegin() , number.rend())){ return num; } //if digits are in ascending order, greatest digit is at last, swap it with first element if( is_sorted(number.begin(), number.end())){ swap( number[number.length() - 1] , number[0]); return stoi(number); } //we need to bring the rightmost max digit to left most index possible //if the starting digits of the numbers are maximum, we dont have to swap them for(int i = 0; i
Beats 69.69% of users in runtime is diabolical
what about beats 100% users 😂 i dont know how their algo works
class Solution {
public int maximumSwap(int num) {
char[] s = Integer.toString(num).toCharArray();
//using post max array
int[] max = new int[s.length];
max[s.length-1] = s.length-1;
for(int i = s.length-2; i>=0; i--){
if(s[i]>s[max[i+1]]){
max[i] = i;
}else{
max[i] = max[i+1];
}
}
for(int i=0; i
Leetcode sometimes goes NUTS... I submitted an O(n^2) code and it beats 100% of users.
"tell me why?" this cant be swapped ---was very needed sir
Leetcode is crazy, it passed my O(n^2) solution which beats 96.08%🤣🤣🤣
The inputs are 4 to 8 digits, the complexity doesn't matter.
i mean the max no is of 9 digits so its just 9 * 9 ie 81.. lolzz
just 5 line yield brute forse couse O(9**2): class Solution: def maximumSwap(c, _: int) -> int: def c():#brute force couse b
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
Summary
Input Conversion: Convert the number to a list of characters for easy manipulation.
Last Occurrence Tracking: Create a dictionary to track the last index of each digit.
Digit Traversal: Iterate through each digit and check if a larger digit exists to the right.
Swapping: If a larger digit is found, swap it with the current digit and return the new number immediately.
Return Original: If no swap occurs, return the original number.
Time and Space Complexity
Time Complexity: The outer loop runs for each digit, and the inner loop checks digits from 9 down to the current digit. In the worst case, this leads to O(n⋅10)=O(n) where n is the number of digits in num.
Space Complexity: The space used for last dictionary is O(1) because it can only contain at most 10 entries (for digits 0-9). The list num_list requires O(n) space, where n is the number of digits. Hence, the overall space complexity is O(n).
Thank you, everytime I see one of this, I get so excited. ;)
*everytime
@@pjp13579 thank you
69.69%
Nicecode
Just curious -- how did you know the problem of the day so quickly?
brute force, he has these problems pre solved..
@@aizad786iqbal not the optimal solution ...
QID Question name Asked Date
349 Intersection Of Two Arrays
632 Smallest Range Covering Elements From K Lists 2024-10-13
641 Design Circular Deque
930 Binary Subarrays With Sum
962 Maximum Width Ramp 2024-10-10
1105 Filling Bookcase Shelves
1233 Remove Sub Folders From The Filesystem
1277 Count Square Submatrices With All Ones
1608 Special Array With X Elements Greater Than Or Equal X
1671 Minimum Number Of Removals To Make Mountain Array
1942 The Number Of The Smallest Unoccupied Chair 2024-10-11
2044 Count Number Of Maximum Bitwise Or Subsets
2406 Divide Intervals Into Minimum Number Of Groups 2024-10-12
2416 Sum Of Prefix Scores Of Strings
2458 Height Of Binary Tree After Subtree Removal Queries
2463 Minimum Total Distance Traveled
2530 Maximal Score After Applying K Operations 2024-10-14
2664 The Knights Tour
2742 Painting The Walls
2838 Maximum Coins Heroes Can Collect 2024-10-08
1593 Split A String Into The Max Number Of Unique Substrings
1963 Minimum Number Of Swaps To Make The String Balanced 2024-10-08
2938 Separate Black And White Balls 2024-10-15
921 Minimum Add To Make Parentheses Valid 2024-10-09
1106 Parsing A Boolean Expression
670 Maximum Swap 2024-10-17
1405 Longest Happy String 2024-10-16
2583 Kth Largest Sum In A Binary Tree
1545 Find Kth Bit In Nth Binary String
687 Longest Univalue Path
968 Binary Tree Cameras
841 Keys And Rooms
Now even you know
@@prajwals8203 where did you get this list?
Seems like extra work at the one pass soln. My algorithm:
- set best to original number
- set max to rightmost digit
- iterate right to left
- update max if necessary
- at every element, if max> el, swap max and el and set best (greatest value)
- return best after loop
Nvm his is more efficient now that I think on it more
was gonna use a heap for some reason spent 30 mins tryna implement it but then got it. thank you
Can you make a video on greedy algorithm with multiple example ? I already have neetcode premium but couldn't find any video on this one?
Technically all the solutions you had would be constant time due to the input being an integer.
Exactly..... i wanted to comment the same thing
I believe despite the input being an integer dose not change the fact that it was converted into string of chars and stored in num which is will take O(n) time, which later is iterated to run the swapping logic on each number on the list already counts as a linear run time along with the join at last when returning the number. Therefore, this solution has three steps which takes O(n) time complexity [O(n) + O(n) + O(n) = O(n)]. So this solution has O(n) time complexity.
List of characters*
@@FlutterInsights doesn’t matter, the length of the string has an upper bound of 10-20 characters based on the type of integer. So it’s O(20) -> O(1)
@ashleywilkonson386 let's go back to basics right, so when the algorithm runs on constant time regardless of an inpute size then we can say that the algorithm has the time complexity of O(n). For eg: let's say there's a function which takes an array of integers of size 1000 but it only returns the specified index arr[12] then it's a constant time regardless of it input size upper bound which is 1000. But let's say if we're trying to find the maximum integer from the array then we need to iterate through each elements of array which means if we go by brut force we will be iterating 1000 times. So here's the difference our first problem only needs to access specifid index of array and return and latter requires to find the max integer, first solution doesn't depend on the input size but latter depends on the input size as we need to loop through the array to get to our expected output. Therefore, the solution on this video takes O(n) time to solve the problem.
Your solutions are intuitive.Thanks
I tried the 2 pass approach after watching this n leetcode gave beats 100% of users, to it
Just changed if-if to if-elif and got 100% in runtime performance.
it is crazy I had 100.00% tc.... LC is funny
Thanks Neetcode, btw anyone wrote the 2pass solution? I was trying to write it. In java but i am confused
class Solution {
public:
int maximumSwap(int num) {
string numStr = to_string(num);
int n = numStr.size();
vector maxRightIndex(n); // Stores the index of the max digit from
// current position to the end
// First pass: Populate maxRightIndex with the index of the largest
// digit to the right of each position
maxRightIndex[n - 1] = n - 1;
for (int i = n - 2; i >= 0; --i) {
maxRightIndex[i] = (numStr[i] > numStr[maxRightIndex[i + 1]])
? i
: maxRightIndex[i + 1];
}
// Second pass: Find the first place where we can swap to maximize the
// number
for (int i = 0; i < n; ++i) {
if (numStr[i] < numStr[maxRightIndex[i]]) {
swap(numStr[i],
numStr[maxRightIndex[i]]); // Swap to maximize the number
return stoi(numStr); // Return the new number immediately after
// the swap
}
}
return num; // Return the original number if no swap can maximize it
}
};
BRILLIANT
just 5 line yield brute forse couse O(9**2): class Solution: def maximumSwap(c, _: int) -> int: def c():#brute force couse b
why can't it be solved using the max_heap? please do help me wrote code which is passing the sample test cases and giving the correct output for text case no-77 while doing DRY RUN but giving the wrong output
class Solution:
def maximumSwap(self, num: int) -> int:
str_num=list(str(num))
lst=[(-int(e),i) for i,e in enumerate(str_num)]
heapq.heapify(lst)
swap=False
i=0
while lst:
digit,indx=heapq.heappop(lst)
digit=digit*-1
if int(str_num[i])==digit:
i+=1
else:
ind=-1
while lst and -lst[0][0]==digit:
_,ind = heapq.heappop(lst)
if ind != -1:
indx=ind
print(str_num[indx],str_num[i],i,indx)
str_num[i],str_num[indx]=str_num[indx],str_num[i]
break
return int("".join(str_num))
help me is it OK?
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))
why dont you give the optimal solution
Gotta pay for that 😉
Is there a more optimal solution?
@@NeetCodeIO O(LOGN) solution exists.
this isn't the most optimal solution,, we can still obtain a constant space linear time solution as against this linear space solution
great to see the wrong solution as well thanks a lot for that ! really gives us insight
BEATS 100% OF USERS. 💪🎸💢
I think Im completely fine with 2path solution
this is my code for two paths im passing 105/112 cases can anyone help me figure out why this isnt working please?
class Solution:
def maximumSwap(self, num: int) -> int:
number = [int(n) for n in str(num)]
print(number)
max_val = 0
max_index = number.index(max(number))
max_arr = [0 for n in number]
# R -> L storing max array
for i in range(len(number)-1, -1, -1):
if number[i] > max_val:
max_val = number[i]
max_index = i
max_arr[i] = max_val
# L -> R to check all values to the left of max_index
for i in range(max_index):
if number[i] < max_val:
temp = number[i]
number[i] = max_val
number[max_index] = temp
break
out = ""
for n in number:
out += str(n)
return int(out)
is the neetcode website down?
Only for certains ISPs in India. This is an issue with firebase hosting, use neetcode.dev for now please
6:48 we can still keep the track of maxvalue post the index by updating the maxvalue right before the inner loop starts
for(int j =0;jj;i--){
if(s[i]-'0' > s[maxindex]-'0')
maxindex = i;
}
if(s[maxindex]-'0' > s[j]-'0'){
var t = s[maxindex];
s[maxindex] = s[j];
s[j] = t;
break;
}
}
class Solution:
def maximumSwap(self, num: int) -> int:
s = str(num)
sorted_s = ''.join(sorted(s, reverse=True))
r = list(s)
for i in range(len(sorted_s)):
if sorted_s[i] != r[i]:
c = sorted_s[i]
d = r[i]
r[i] = c
for j in range(len(sorted_s) - 1, -1, -1):
if c == r[j] and j != i:
r[j] = d
break
break
return int(''.join(r))
Is this good or not ? 😊
This solution would work, however the bottleneck of this algorithm is the sorting on the start because it takes O(nlogn). A way to optimize this would be to change the sort to a max heap. heapq.heapify function takes O(n) time, which is faster.
@@AlfredPros Actually , the largest number is of length is 9 digit so n=9 in this case, am i right ? So it works in O(1) may be
@@rajGg-h3g n in this case is the digit of num. I thought about the algorithm as general as possible, that's why I said the sorting time is O(nlogn). Since the problem only have 9 digits at maximum, the time difference may not be so apparent at the end.
dofm mgsd g somng m
I too had a stroke when I tried to solve this problem
bro I wrote a 50 line monstrosity. with 2 helper function. and finally it worked OR SO I THOUGHT. but damn there were like 1 test cases which fuked me up fixed it then it broke some other test case best result was 110/112 . wasted 2 hours, kinda solved it but it failed. here i am
EDIT - here is the monstrosity if anyone is interested Do NOT ask me what it is or how it works, coz i myself forgot what this is supposed to do.
```
class Solution {
public:
int firstNonDecreasingIndex(string s) {
for (int i = 0; i < s.length() - 1; i++) {
if (s[i] front1; i--) {
if (s[i] > a) {
a = s[i];
}
}
return a;
}
int maximumSwap(int num) {
string intnum = to_string(num);
string temp = intnum;
int currgreatest = num;
int front = 0, back = intnum.size()-1;
char sl = greatestInt(intnum);
int i = intnum.size()-1;
for (int i = temp.size() - 1; i >= 0; i--) {
if (temp[i] == sl) {
back = i;
break;
}
}
while(front < back){
if (temp[front] < temp[back]){
swap(temp[front], temp[back]);
}
int test = stoi(temp);
if(test > currgreatest){
currgreatest = test;
}
temp = intnum;
front++;
}
return currgreatest;
}
};
```
check out the monstrosity i first wrote:
class Solution {
public:
int findRightMostGreatestChar(const string &str, int startIdx, int endIdx) {
if (startIdx < 0 || endIdx >= str.length() || startIdx > endIdx) {
return -1; // Invalid range
}
char baseChar = str[startIdx]; // Set base char as str[startIdx]
int resultIdx = -1; // To store the index of the rightmost greatest char
char maxChar = baseChar; // Initially set maxChar as baseChar
// Traverse the substring from startIdx to endIdx (right to left)
for (int i = endIdx; i > startIdx; --i) {
if (str[i] > maxChar) {
maxChar = str[i]; // Update maxChar to the current greatest character
resultIdx = i; // Update resultIdx to the rightmost index of the greatest character
}
}
return resultIdx; // Return the index of the rightmost greatest character
}
int maximumSwap(int num) {
string number = to_string(num);
//if digits are in descending order, no greater number is possible
if( is_sorted( number.rbegin() , number.rend())){
return num;
}
//if digits are in ascending order, greatest digit is at last, swap it with first element
if( is_sorted(number.begin(), number.end())){
swap( number[number.length() - 1] , number[0]);
return stoi(number);
}
//we need to bring the rightmost max digit to left most index possible
//if the starting digits of the numbers are maximum, we dont have to swap them
for(int i = 0; i
just 5 line yield brute forse couse O(9**2): class Solution: def maximumSwap(c, _: int) -> int: def c():#brute force couse b
Sus