Maximum Swap [Medium] — Rightmost Digit Tracking

Problem Statement

You can swap two digits at most once to make the number as large as possible. Return the maximum value.

Input: 2736 → Output: 7236
Input: 9973 → Output: 9973

Intuition

Build a map of digit → last occurrence index. Scan left to right; for each digit, check if a larger digit exists to the right (use last occurrence map). Swap and return.

Solutions

C++

int maximumSwap(int num) {
    string s = to_string(num);
    int last[10]={};
    for (int i=0;i<s.size();i++) last[s[i]-'0']=i;
    for (int i=0;i<s.size();i++)
        for (int d=9;d>s[i]-'0';d--)
            if (last[d]>i) { swap(s[i],s[last[d]]); return stoi(s); }
    return num;
}

Java

public int maximumSwap(int num) {
    char[] s=Integer.toString(num).toCharArray();
    int[] last=new int[10];
    for (int i=0;i<s.length;i++) last[s[i]-'0']=i;
    for (int i=0;i<s.length;i++)
        for (int d=9;d>s[i]-'0';d--)
            if (last[d]>i){char t=s[i];s[i]=s[last[d]];s[last[d]]=t;return Integer.parseInt(new String(s));}
    return num;
}

Python

def maximumSwap(num: int) -> int:
    s = list(str(num))
    last = {int(d): i for i, d in enumerate(s)}
    for i, c in enumerate(s):
        for d in range(9, int(c), -1):
            if last.get(d, -1) > i:
                j = last[d]
                s[i], s[j] = s[j], s[i]
                return int(''.join(s))
    return num

Complexity

Time: O(n) (n = number of digits)
Space: O(n)