Maximum Swap

670.Maximum Swap

String

Greedy

Math

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:

Input:

num = 2736

→

Output:

7236

Algorithm:

1. Convert number to string for manipulation
2. Scan right to left tracking largest digit
3. Find position for optimal swap
4. Perform swap if beneficial

Complexity:

Time: O(n) | Space: O(n) where n is number of digits

Java Solution:

public int maximumSwap(int num) {
    StringBuilder sb = new StringBuilder(String.valueOf(num));

    int maxIndex = -1, swapIdx1 = -1, swapIdx2 = -1;

    // Traverse right to left tracking max digit and potential swap
    for (int i = sb.length() - 1; i >= 0; --i) {
        char c = sb.charAt(i);
        if (maxIndex == -1 || sb.charAt(i) > sb.charAt(maxIndex)) {
            maxIndex = i;  // Update max digit index
        } else if (sb.charAt(i) < sb.charAt(maxIndex)) {
            swapIdx1 = i;  // Mark smaller digit
            swapIdx2 = maxIndex;  // Mark larger digit
        }
    }

    // Perform swap if beneficial
    if (swapIdx1 != -1 && swapIdx2 != -1) 
        swap(sb, swapIdx1, swapIdx2);
    
    return Integer.parseInt(sb.toString());
}

private void swap(StringBuilder sb, int a, int b) {
    char temp = sb.charAt(a);
    sb.setCharAt(a, sb.charAt(b));
    sb.setCharAt(b, temp);
}

Python Solution:

def maximumSwap(self, num: int) -> int:
    nums = list(str(num))  # Convert to list for manipulation
    max_idx = -1
    swap_idx1 = swap_idx2 = -1
    
    for i in range(len(nums)-1, -1, -1):
        if max_idx == -1 or nums[i] > nums[max_idx]:
            max_idx = i
        elif nums[i] < nums[max_idx]:
            swap_idx1 = i
            swap_idx2 = max_idx
            
    if swap_idx1 != -1:
        nums[swap_idx1], nums[swap_idx2] = nums[swap_idx2], nums[swap_idx1]
        
    return int(''.join(nums))

C++ Solution:

class Solution {
public:
    int maximumSwap(int num) {
        string nums = to_string(num);
        int max_idx = -1;
        int swap_idx1 = -1, swap_idx2 = -1;
        
        for(int i = nums.length()-1; i >= 0; i--) {
            if(max_idx == -1 || nums[i] > nums[max_idx]) {
                max_idx = i;
            } else if(nums[i] < nums[max_idx]) {
                swap_idx1 = i;
                swap_idx2 = max_idx;
            }
        }
        
        if(swap_idx1 != -1) {
            swap(nums[swap_idx1], nums[swap_idx2]);
        }
        
        return stoi(nums);
    }
};