grid47 Exploring patterns and algorithms
Sep 1, 2024
6 min read
Solution to LeetCode 670: Maximum Swap Problem
You are given an integer num, and you can swap two digits at most once to get the largest possible number. Return the maximum number that can be obtained after performing the swap.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer `num` which is the number whose digits need to be rearranged by swapping at most two digits to get the maximum value.
Example: num = 1234
Constraints:
• 0 <= num <= 10^8
Output: Return the largest number that can be obtained by swapping two digits in the number at most once.
Example: 4231
Constraints:
• The number must be returned as an integer.
Goal: Maximize the number by swapping two digits at most once.
Steps:
• 1. Convert the number into a string to easily access individual digits.
• 2. Track the index of the largest possible digit that can be swapped for each position.
• 3. For each digit, check if a swap is possible with any larger digit from a later position.
• 4. Perform the swap and return the resulting number.
Goal: The problem ensures that the number is within the specified range and only allows one swap of two digits.
Steps:
• The integer `num` has at most 8 digits (0 <= num <= 10^8).
Assumptions:
• The number is a non-negative integer.
• Input: num = 1234
• Explanation: The maximum number can be obtained by swapping the digits 1 and 4, resulting in 4231.
• Input: num = 9876
• Explanation: Since the number is already in the maximum possible order, no swap is needed, and the result is 9876.
Approach: To solve this problem, we need to find the largest number by performing at most one swap between two digits of the number.
Observations:
• The approach involves checking the possibility of swapping each digit with the largest available digit from the right side.
• If a swap can maximize the number, we perform the swap and return the result.
Steps:
• 1. Convert the number into a string to manipulate individual digits.
• 2. Use an array to track the rightmost index of each digit from 0 to 9.
• 3. Traverse the number from left to right, and for each digit, check if there is a larger digit to swap with from the right.
• 4. If such a swap is found, perform the swap and return the result.
Empty Inputs:
• There are no empty inputs in this problem, as the number is always provided.
Large Inputs:
• Ensure the solution handles numbers with up to 8 digits (max 10^8).
Special Values:
• If the number is already the largest possible form, no swap should be made.
Constraints:
• The number will be within the range 0 <= num <= 10^8.
This is the function definition for `maximumSwap`, which takes an integer `num` and returns the largest number that can be obtained by swapping two digits of `num` at most once.
2 : Initialization of Array
An integer vector `idx` of size 10 is initialized to store the index positions of the last occurrence of each digit from 0 to 9 in the number.
3 : Index Array Initialization
vector<int> idx(10, 0);
A vector `idx` is created and initialized to store the last index of each digit in the number `num`.
4 : Convert Number to String
The number `num` is converted to a string so that we can easily iterate through its digits.
5 : String Conversion
string nm = to_string(num);
Convert the number `num` into a string `nm` to facilitate manipulation of individual digits.
6 : Tracking Digit Indices
for(int i =0; i < nm.size(); i++) idx[nm[i] -'0'] = i;
Iterate through each digit of the string `nm` and store its index in the `idx` array. This ensures that we know the position of each digit's last occurrence.
7 : Main Loop
The outer loop iterates through the digits of `nm` from left to right to determine which digits can be swapped for maximizing the number.
8 : Outer Loop
for(int i =0; i < nm.size(); i++)
This loop iterates through each digit of `nm` to determine if a larger digit can be swapped with it to form a larger number.
9 : Inner Loop
for(int j =9; j > nm[i] -'0'; j--) {
The inner loop looks for a larger digit, from 9 to the current digit, that appears later in the string to swap with the current digit.
10 : Check for Valid Swap
if(idx[j] > i) {
If a digit larger than the current digit is found later in the string (`idx[j] > i`), this means we can swap these digits to form a larger number.
11 : Perform Swap
swap(nm[idx[j]], nm[i]);
Swap the current digit `nm[i]` with the larger digit found later in the string `nm[idx[j]]`.
12 : Return Maximized Number
returnstoi(nm);
Convert the modified string back to an integer and return it as the result, representing the maximum number that can be obtained by one swap.
13 : Return Original Number
return num;
Return the original number `num` if no valid swap was found that can maximize the number.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of digits in the number. Since the number has at most 8 digits, this is efficient.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1), as we only use a constant amount of extra space.
