Last updated on February 20th, 2025 at 09:12 am
Here, we see a Maximum Swap LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Math
Companies
Level of Question
Medium
Maximum Swap LeetCode Solution
Table of Contents
1. 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.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Greedy Algorithm where we make a locally optimal choice (the best swap) at each step to achieve the globally optimal solution (the maximum number).. The goal is to maximize the number by swapping at most one pair of digits. The algorithm greedily identifies the best possible swap to achieve the maximum number.
3. Code Implementation in Different Languages
3.1 Maximum Swap C++
class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
string s1 = s;
for(int i=0;i<s.length();i++)
{
int temp = getmax(s,i);
swap(s[i],s[temp]);
if(s1!=s)
break;
}
int number = stoi(s);
return number;
}
static int getmax(string s, int i){
int max=i;
for(int j=i;j<s.length();j++)
{
if(s[max]<=s[j])
max=j;
}
return max;
}
};
3.2 Maximum Swap Java
class Solution {
public int maximumSwap(int num) {
if(num < 10) return num;
char[] arr = String.valueOf(num).toCharArray();
int[] rightIndex = new int[10];
for(int i=0; i<arr.length; i++){
rightIndex[arr[i] - '0'] = i;
}
for(int i=0; i<arr.length; i++){
for(int j=9; j>arr[i] - '0'; j--){
if(rightIndex[j] > i){
char temp = arr[i];
arr[i] = arr[rightIndex[j]];
arr[rightIndex[j]] = temp;
return Integer.valueOf(new String(arr));
}
}
}
return num;
}
}
3.3 Maximum Swap JavaScript
var maximumSwap = function(num) {
const digits = num.toString().split("");
let max = -1, maxIdx = -1, leftIdx = -1, rightIdx = -1;
for(let i = digits.length - 1; i >= 0; i--) {
const digit = parseInt(digits[i]);
if(digit > max) max = digit, maxIdx = i;
else if(digit < max) leftIdx = i, rightIdx = maxIdx;
}
if(leftIdx === -1) return num;
[digits[leftIdx],digits[rightIdx]] = [digits[rightIdx],digits[leftIdx]];
return parseInt(digits.join(""));
};
3.4 Maximum Swap Python
class Solution(object):
def maximumSwap(self, num):
s = list(str(num))
n = len(s)
for i in range(n-1):
if s[i] < s[i+1]: break
else: return num
max_idx, max_val = i+1, s[i+1]
for j in range(i+1, n):
if max_val <= s[j]: max_idx, max_val = j, s[j]
left_idx = i
for j in range(i, -1, -1):
if s[j] < max_val: left_idx = j
s[max_idx], s[left_idx] = s[left_idx], s[max_idx]
return int(''.join(s))
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n²) | O(n) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |
- C++ Implementation is less efficient due to the repeated calls to
getmax, which results in O(n²) time complexity. - Java, JavaScript, and Python Implementations are more efficient with O(n) time complexity due to precomputations or single-pass logic.
- All implementations use O(n) space for storing the digits of the number as a string or array.