Maximum Swap - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You’re given a non‑negative integer. You may swap two digits at most once. The goal is to produce the largest possible number after that swap. If no beneficial swap exists, return the original number.
Approach 1: Brute Force Digit Swap (O(n^2) time, O(n) space)
Convert the number into a digit array so individual positions are easy to manipulate. Try every possible pair of indices (i, j) where i < j, swap the digits, and compute the resulting number. Track the maximum value across all swaps. After each test swap, revert the digits to continue exploring other combinations.
This works because there are only n(n-1)/2 possible swaps for n digits. However, recomputing the number after each swap makes the solution quadratic. It’s acceptable for small inputs but inefficient compared to a targeted strategy. Still, implementing this first often helps clarify the problem constraints before applying a greedy optimization.
Approach 2: Greedy Using Last Occurrence (O(n) time, O(1) space)
The key insight: for each digit, the best swap is with the largest possible digit that appears later in the number. Instead of testing all pairs, record the last occurrence index of each digit 0–9. This gives constant‑time access to the rightmost position of any digit.
Scan the digits from left to right. For the current digit d, check if a larger digit (from 9 down to d+1) appears later using the last‑occurrence map. If such a digit exists at position j > i, swapping digits[i] with digits[j] produces the largest improvement at the earliest place value. Perform the swap and stop immediately because only one swap is allowed.
This greedy rule works because improving a more significant digit always dominates any changes to less significant digits. By checking digits in descending order and using their last positions, you ensure the swap yields the maximum possible number. The algorithm runs in linear time and constant extra space, making it ideal for interview settings and large inputs. The reasoning relies on place value properties from math and a classic greedy choice strategy often used in array manipulation problems (arrays).
Recommended for interviews: The greedy last‑occurrence approach is the expected solution. It demonstrates recognition of the optimal swap position and reduces the search from quadratic to linear time. Mentioning the brute force method first shows problem exploration, while implementing the greedy version shows algorithmic maturity.
Approach 1: Greedy Approach Using Last Occurrence
The idea is to always try and bring the largest possible digit to the leftmost position if it maximizes the number. For this, we can use a map to record the last occurrence of each digit. By iterating through the number, we can then attempt swapping if any larger digit occurs later.
We convert the number to a string of digits and map each digit to its last occurrence in the number. We then iterate through the digits, looking for any larger digit that comes after the current one. If found, we swap them to create the largest possible number.
Complexity
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(1) as the storage is constant due to limited digit size.
Approach 2: Greedy Algorithm
First, we convert the number into a string s. Then, we traverse the string s from right to left, using an array or hash table d to record the position of the maximum number to the right of each number (it can be the position of the number itself).
Next, we traverse d from left to right. If s[i] < s[d[i]], we swap them and exit the traversal process.
Finally, we convert the string s back into a number, which is the answer.
The time complexity is O(log M), and the space complexity is O(log M). Here, M is the range of the number num.
Approach 3: Space Optimized Greedy
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Last Occurrence | Time Complexity: O(n), where n is the number of digits in num. |
| Greedy Algorithm | — |
| Space Optimized Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Digit Swap | O(n^2) | O(n) | Useful for understanding the problem or when input size is very small |
| Greedy Using Last Occurrence | O(n) | O(1) | Optimal solution for interviews and production code |
Video Solution
Maximum Swaps - Leetcode 670 - Python • NeetCodeIO • 25,255 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Swap easy or hard?
How to solve Maximum Swap in O(n)?
What is the best approach for Maximum Swap?
What data structure is used in Maximum Swap?
What is the time complexity of Maximum Swap?
Maximum Swap Python or Java solution approach?
Is Maximum Swap asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Maximum Swap with our built-in code editor and test cases.
Practice on FleetCode