Maximum Swap
MedPrompt
You are given an integer num. You can swap two digits at most once to get the maximum valued number.
Return the maximum valued number you can get.
Example 1:
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.Example 2:
Input: num = 9973
Output: 9973
Explanation: No swap.
Constraints:
0 <= num <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
This approach exhaustively tries every possible single swap. It iterates through all pairs of digits, swaps them, and evaluates the resulting number. The maximum number found after trying all swaps is the answer. This method guarantees finding the correct answer by exploring the entire search space of single swaps.
Algorithm
- Convert the input number
numinto a character arrays. - Initialize a variable
maxValwith the originalnum. - Use two nested loops to generate all possible unique pairs of indices
(i, j)wherei < j. - For each pair
(i, j):- Create a temporary copy of the character array
s. - Swap the characters at indices
iandjin the copy. - Convert the modified character array back into an integer.
- Update
maxValto be the maximum of its current value and the newly formed integer.
- Create a temporary copy of the character array
- After iterating through all possible swaps,
maxValwill hold the largest number achievable with at most one swap.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We begin by converting the integer into a sequence of characters, which is easier to manipulate. We then systematically try swapping every digit with every other digit that comes after it. For each swap, we form a new number and compare it with the maximum number we've seen so far. To ensure the original sequence is available for the next pair-swap, we either use a copy of the array for each swap or swap the digits back to their original positions after evaluating the new number. The initial number is also a candidate for the maximum, covering the case where no swap is beneficial.
class Solution { public int maximumSwap(int num) { char[] digits = String.valueOf(num).toCharArray(); int maxNum = num; for (int i = 0; i < digits.length; i++) { for (int j = i + 1; j < digits.length; j++) { // Swap char temp = digits[i]; digits[i] = digits[j]; digits[j] = temp; // Update max maxNum = Math.max(maxNum, Integer.parseInt(new String(digits))); // Swap back to restore the original array for the next iteration temp = digits[i]; digits[i] = digits[j]; digits[j] = temp; } } return maxNum; }}Complexity
Time
O(N^3), where N is the number of digits in `num`. There are O(N^2) pairs of digits to swap. For each swap, converting the character array to a string and then to an integer takes O(N) time.
Space
O(N), where N is the number of digits in `num`. This space is used to store the character array representation of the number.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct as it checks all possibilities.
Cons
The time complexity is cubic in the number of digits, making it inefficient, although it passes for the given constraints.
It performs many unnecessary calculations and conversions.
A greedy approach works by making the locally optimal choice at each step. To maximize the number, we want to place the largest possible digits at the most significant (leftmost) positions. We scan the number from left to right. For each digit, we look for the largest digit to its right. If we find a digit that is smaller than a digit to its right, we've identified a candidate for a swap. We should swap this digit with the largest digit to its right (specifically, the rightmost occurrence of that largest digit) to create the biggest possible number. This swap is performed on the first such digit we find from the left, as this yields the most significant improvement.
Algorithm
- Convert the input number
numto a character arrayA. - Iterate through the array
Afrom left to right with an indexi. - For each
i, find the indexmax_idxof the largest digit in the subarray to its right (A[i+1]toA[n-1]). To ensure the resulting number is maximized, if the largest digit appears multiple times,max_idxshould point to its rightmost occurrence. - Check if the digit at the current position
A[i]is smaller than the largest digit found to its rightA[max_idx]. - If it is, this is the first (leftmost) position that can be improved. Swap
A[i]withA[max_idx]. - Since only one swap is allowed and we have just performed the most impactful one, convert the modified array
Aback to an integer and return it immediately. - If the loop completes without any swaps, the number's digits are already in descending order. Return the original
num.
Walkthrough
This greedy strategy is more efficient than brute force. We convert the number to a character array and iterate from left to right. For each digit A[i], we scan the rest of the array to its right to find the largest digit available for a swap. If the largest digit to the right is greater than A[i], we perform the swap. The key is to find the leftmost digit A[i] that is smaller than some digit to its right, and swap it with the largest of those digits. To handle cases like 1993 where we want 9913 not 9193, we must swap with the rightmost occurrence of the target digit. Once the single, most effective swap is done, the process terminates.
class Solution { public int maximumSwap(int num) { char[] digits = String.valueOf(num).toCharArray(); int n = digits.length; for (int i = 0; i < n; i++) { int maxIdx = i; // Find the index of the largest digit to the right of i for (int j = i + 1; j < n; j++) { // Use >= to ensure we get the rightmost occurrence of the max digit if (digits[j] >= digits[maxIdx]) { maxIdx = j; } } // If a larger digit is found to the right, swap and return if (digits[i] < digits[maxIdx]) { char temp = digits[i]; digits[i] = digits[maxIdx]; digits[maxIdx] = temp; return Integer.parseInt(new String(digits)); } } // If no swap was made, the number is already the largest return num; }}Complexity
Time
O(N^2), where N is the number of digits. The nested loops lead to a quadratic runtime. The outer loop runs N times, and the inner loop runs up to N times.
Space
O(N), where N is the number of digits. This space is for the character array.
Trade-offs
Pros
More efficient than the brute-force approach.
Relatively easy to reason about the greedy choice.
Cons
The time complexity is quadratic, which is not optimal.
This is an optimized version of the greedy approach that achieves linear time complexity. The core idea is the same: find the leftmost digit that can be swapped with a larger digit to its right to form a bigger number. Instead of repeatedly scanning for the largest digit in a nested loop, we pre-process the number to find the last known index of each digit (0-9). With this information, for each digit, we can determine in constant time if a better digit exists to its right and where its rightmost position is. This eliminates the quadratic complexity.
Algorithm
- Convert the input number
numto a character arrayA. - Create an integer array
last_occurrenceof size 10, initialized to 0. - Iterate through
Afrom left to right to populatelast_occurrence, wherelast_occurrence[d]will store the index of the last time digitdwas seen. - Iterate through
Aagain from left to right (indexi). Thisirepresents the position we are trying to swap from. - For each digit
A[i], look for a larger digitdthat could be swapped into this position. We do this by iteratingdfrom 9 down toA[i] - '0' + 1. - For each
d, check if its last occurrence is to the right ofi(i.e.,last_occurrence[d] > i). - If such a
dis found, we have identified the best possible swap: swapA[i]with the digit atA[last_occurrence[d]]. - After the swap, convert the array
Aback to an integer and return it, as we have found the maximum value. - If the loops complete without any swap, the number is already optimal. Return the original
num.
Walkthrough
The linear time solution refines the greedy strategy by being smarter about finding the swap target. First, we pass through the number (as a character array) to record the last index of each digit in a separate last_occurrence array. This takes O(N) time. Then, we iterate through the character array a second time, from left to right. For each digit A[i], we check if there's a larger digit (from 9 down to A[i]+1) whose last occurrence is to the right of i. The first time we find such a case, we've found our optimal swap. We swap A[i] with that larger digit and return the resulting number. This check is fast because we can directly look up the position from our last_occurrence array.
class Solution { public int maximumSwap(int num) { char[] digits = String.valueOf(num).toCharArray(); int n = digits.length; int[] lastOccurrence = new int[10]; // Record the last index of each digit for (int i = 0; i < n; i++) { lastOccurrence[digits[i] - '0'] = i; } // Find the first position from the left that can be swapped for a larger digit for (int i = 0; i < n; i++) { int currentDigit = digits[i] - '0'; // Try to find a larger digit (from 9 down to currentDigit+1) for (int d = 9; d > currentDigit; d--) { // If a larger digit exists to the right of the current position if (lastOccurrence[d] > i) { // Swap with the rightmost occurrence of that larger digit char temp = digits[i]; digits[i] = digits[lastOccurrence[d]]; digits[lastOccurrence[d]] = temp; return Integer.parseInt(new String(digits)); } } } // If no swap was made, the number is already the largest return num; }}Complexity
Time
O(N), where N is the number of digits. Populating the `last_occurrence` array takes O(N). The main loop runs N times, and its inner loop runs at most 10 times (a constant), so the total time is O(N).
Space
O(N), where N is the number of digits. O(N) is for the character array, and the `last_occurrence` array takes O(1) space as its size (10) is constant.
Trade-offs
Pros
Optimal time complexity.
Very efficient, solving the problem with a constant number of passes over the digits.
Cons
Slightly more complex to conceptualize due to the pre-computation step.
Solutions
Solution
class Solution {public int maximumSwap(int num) { char[] s = String.valueOf(num).toCharArray(); int n = s.length; int[] d = new int[n]; for (int i = 0; i < n; ++i) { d[i] = i; } for (int i = n - 2; i >= 0; --i) { if (s[i] <= s[d[i + 1]]) { d[i] = d[i + 1]; } } for (int i = 0; i < n; ++i) { int j = d[i]; if (s[i] < s[j]) { char t = s[i]; s[i] = s[j]; s[j] = t; break; } } return Integer.parseInt(String.valueOf(s)); }}class Solution {public: int maximumSwap(int num) { string s = to_string(num); int n = s.size(); vector<int> d(n); iota(d.begin(), d.end(), 0); for (int i = n - 2; ~i; --i) { if (s[i] <= s[d[i + 1]]) { d[i] = d[i + 1]; } } for (int i = 0; i < n; ++i) { int j = d[i]; if (s[i] < s[j]) { swap(s[i], s[j]); break; } } return stoi(s); }};class Solution: def maximumSwap(self, num: int) -> int: s = list(str(num)) n = len(s) d = list(range(n)) for i in range(n - 2, - 1, - 1): if s[i] <= s[d[i + 1]]: d[i] = d[i + 1] for i, j in enumerate(d): if s[i] < s[j]: s[i], s[j] = s[j], s[i] break return int('' . join(s))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.