Maximum Swap solution and explanation
Google
TCS
9 more videos on this problem
Maximum Swaps - Leetcode 670 - PythonNeetCodeIO · 15:40 · 25K views
Maximum Swap | 2 Simple Approaches | Leetcode 670 | codestorywithMIKcodestorywithMIK · 26:14 · 11K views
MAXIMUM SWAP | LEETCODE 670 | PYTHON SOLUTIONCracking FAANG · 15:12 · 9K views
Leetcode #670 - Maximum Swap (Solution)Algorithms Illustrator · 19:36 · 8K views
Maximum Swap | 4 techniques | Leetcode 670Techdose · 19:05 · 5K views
670. Maximum Swap | Leetcode Daily Challenge | DSA | Java | FAANGShashCode · 17:24 · 4K views
LeetCode 670. Maximum SwapHappy Coding · 20:52 · 3K views
Leetcode 670 Maximum SwapRen Zhang · 17:32 · 2K views
Maximum Swap | LeetCode 670 | PythonBreathAlgos · 8:14 · 1K views
LeetCode 670. Maximum Swap | JSer - JavaScript & AlgorithmJSer · 14:55 · 394 views
The problem
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.
class Solution:
def maximumSwap(self, num: int) -> int:
digits = list(str(num))
last = {int(x): i for i, x in enumerate(digits)}
for i, x in enumerate(digits):
for d in range(9, int(x), -1):
if last.get(d, 0) > i:
digits[i], digits[last[d]] = digits[last[d]], digits[i]
return int(''.join(digits))
return num
sol = Solution()
num = 2736
print(sol.maximumSwap(num))public class Solution {
public int maximumSwap(int num) {
char[] digits = Integer.toString(num).toCharArray();
int[] last = new int[10];
for (int i = 0; i < digits.length; i++) {
last[digits[i] - '0'] = i;
}
for (int i = 0; i < digits.length; i++) {
for (int d = 9; d > digits[i] - '0'; d--) {
if (last[d] > i) {
char tmp = digits[i];
digits[i] = digits[last[d]];
digits[last[d]] = tmp;
return Integer.parseInt(new String(digits));
}
}
}
return num;
}
public static void main(String[] args) {
Solution sol = new Solution();
int num = 2736;
System.out.println(sol.maximumSwap(num));
}
}#include <iostream>
#include <vector>
using namespace std;
int maximumSwap(int num) {
string digits = to_string(num);
vector<int> last(10, 0);
int n = digits.length();
for (int i = 0; i < n; i++) {
last[digits[i] - '0'] = i;
}
for (int i = 0; i < n; i++) {
for (int d = 9; d > digits[i] - '0'; d--) {
if (last[d] > i) {
swap(digits[i], digits[last[d]]);
return stoi(digits);
}
}
}
return num;
}
int main() {
int num = 2736;
cout << maximumSwap(num) << endl;
return 0;
}function maximumSwap(num) {
let digits = Array.from(String(num), Number);
let last = Array(10).fill(0);
for (let i = 0; i < digits.length; i++) {
last[digits[i]] = i;
}
for (let i = 0; i < digits.length; i++) {
for (let d = 9; d > digits[i]; d--) {
if (last[d] > i) {
[digits[i], digits[last[d]]] = [digits[last[d]], digits[i]];
return parseInt(digits.join(''));
}
}
}
return num;
}
let num = 2736;
console.log(maximumSwap(num));#include <stdio.h>
#include <string.h>
int maximumSwap(int num) {
char digits[10];
sprintf(digits, "%d", num);
int last[10] = {0};
int len = strlen(digits);
for (int i = 0; i < len; i++) {
last[digits[i] - '0'] = i;
}
for (int i = 0; i < len; i++) {
for (int d = 9; d > digits[i] - '0'; d--) {
if (last[d] > i) {
char temp = digits[i];
digits[i] = digits[last[d]];
digits[last[d]] = temp;
return atoi(digits);
}
}
}
return num;
}
int main() {
int num = 2736;
printf("%d\n", maximumSwap(num));
return 0;
}using System;
public class Solution {
public int MaximumSwap(int num) {
char[] digits = num.ToString().ToCharArray();
int[] last = new int[10];
for (int i = 0; i < digits.Length; i++) {
last[digits[i] - '0'] = i;
}
for (int i = 0; i < digits.Length; i++) {
for (int d = 9; d > digits[i] - '0'; d--) {
if (last[d] > i) {
char temp = digits[i];
digits[i] = digits[last[d]];
digits[last[d]] = temp;
return int.Parse(new string(digits));
}
}
}
return num;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int num = 2736;
Console.WriteLine(sol.MaximumSwap(num));
}
}Python's dictionary comprehension allows us to easily map digits to their last occurrence. The solution involves iterating over the digits and applying a swapping strategy to achieve the largest number.
Time Complexity: O(n)
Space Complexity: O(1)
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.
function maximumSwap(num: number): number {
const list = new Array();
while (num !== 0) {
list.push(num % 10);
num = Math.floor(num / 10);
}
const n = list.length;
const idx = new Array();
for (let i = 0, j = 0; i < n; i++) {
if (list[i] > list[j]) {
j = i;
}
idx.push(j);
}
for (let i = n - 1; i >= 0; i--) {
if (list[idx[i]] !== list[i]) {
[list[idx[i]], list[i]] = [list[i], list[idx[i]]];
break;
}
}
let res = 0;
for (let i = n - 1; i >= 0; i--) {
res = res * 10 + list[i];
}
return res;
}func maximumSwap(num int) int {
s := []byte(strconv.Itoa(num))
n := len(s)
d := make([]int, n)
for i := range d {
d[i] = i
}
for i := n - 2; i >= 0; i-- {
if s[i] <= s[d[i+1]] {
d[i] = d[i+1]
}
}
for i, j := range d {
if s[i] < s[j] {
s[i], s[j] = s[j], s[i]
break
}
}
ans, _ := strconv.Atoi(string(s))
return ans
}impl Solution {
pub fn maximum_swap(mut num: i32) -> i32 {
let mut list = {
let mut res = Vec::new();
while num != 0 {
res.push(num % 10);
num /= 10;
}
res
};
let n = list.len();
let idx = {
let mut i = 0;
(0..n)
.map(|j| {
if list[j] > list[i] {
i = j;
}
i
})
.collect::<Vec<usize>>()
};
for i in (0..n).rev() {
if list[i] != list[idx[i]] {
list.swap(i, idx[i]);
break;
}
}
let mut res = 0;
for i in list.iter().rev() {
res = res * 10 + i;
}
res
}
}Approach 3: Space Optimized Greedy
function maximumSwap(num: number): number {
const ans = [...String(num)];
let [min, max, maybeMax, n] = [-1, -1, -1, ans.length];
for (let i = n - 1; i >= 0; i--) {
if (ans[i] > (ans[maybeMax] ?? -1)) maybeMax = i;
if (i < maybeMax && ans[i] < ans[maybeMax]) {
[min, max] = [i, maybeMax];
}
}
if (~min && ~max && min < max) {
[ans[min], ans[max]] = [ans[max], ans[min]];
}
return +ans.join('');
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Last Occurrence | Time Complexity: O(n) |
| Greedy Algorithm | – |
| Space Optimized Greedy | – |
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 |
Frequently asked questions
Is Maximum Swap easy or hard?
Maximum Swap is generally classified as a Medium difficulty problem. The brute-force solution is straightforward, but identifying the greedy optimization using the last occurrence of digits requires understanding how place value affects the final number.
How to solve Maximum Swap in O(n)?
Convert the integer into a digit array and record the last index of each digit from 0 to 9. Iterate from the leftmost digit and check if a larger digit appears later using the stored indices. Swap with the largest possible digit’s last occurrence and stop immediately. This guarantees the maximum improvement in linear time.
What is the best approach for Maximum Swap?
The greedy last-occurrence approach is the best solution. Record the last position of each digit (0–9), then scan the number from left to right and swap the current digit with the largest digit appearing later. This guarantees the maximum possible number using only one swap and runs in O(n) time with O(1) extra space.
What data structure is used in Maximum Swap?
The optimal solution uses a small array or hash map to store the last occurrence of digits 0–9. The number itself is usually converted into a character or integer array so digits can be swapped efficiently.
What is the time complexity of Maximum Swap?
The optimal greedy solution runs in O(n) time where n is the number of digits. A single pass records the last occurrence of each digit, and another pass determines the best swap. Space complexity remains O(1) because the digit lookup array has a fixed size of 10.
Maximum Swap Python or Java solution approach?
Both Python and Java implementations follow the same greedy strategy: convert the number to a digit array, build a last-occurrence array for digits, scan from left to right, and perform one swap with the largest later digit. The algorithm remains O(n) time and O(1) extra space regardless of language.
Is Maximum Swap asked at Google, Amazon, or Meta?
Maximum Swap appears in interview preparation sets for companies like Amazon, Google, and Meta because it tests greedy reasoning and digit manipulation. It’s commonly used to evaluate whether candidates can reduce a brute-force search into a linear-time greedy strategy.