Maximum Swap

Leetcode Problem:

• Maximum Swap

Summary

• Given an integer, find the maximum valued number by swapping two digits at most once.

Approach

• Use a stack to store the digits of the input number, and then iterate through the stack to find the largest possible swap
• If a swap is possible, perform it and return the result
• If no swap is possible, return the original number.

Complexity

• O(log n) where n is the input number, because we are iterating through the stack and performing constant time operations for each digit.

Explanation

• The solution uses a stack to store the digits of the input number
• It starts by pushing the digits onto the stack in reverse order, along with their corresponding powers of 10
• Then, it iterates through the stack to find the largest possible swap
• If a swap is possible, it performs the swap and returns the result
• If no swap is possible, it returns the original number.

Solution Code:

struct number{
    int n;
    int pow;
};
struct _stack{
    number arr[20];
    int top;
    _stack(){
        top = 0;
    }
    void push(number a){
        arr[top++] = a;
    }
    number pop(){
        return arr[--top];
    }
    number peek(){
        return arr[top - 1];
    }
    bool empty(){
        return top == 0;
    }
};


class Solution {
public:
    _stack st;
    int maximumSwap(int num) {
        vector mostRight;
        int tmpNum = num;
        int pow = 1;
        while(tmpNum){
            int n = tmpNum % 10;
            while (!st.empty() && st.peek().n < n){
                st.pop();
            }
            if(st.empty()){
                st.push({n, pow});
                mostRight.push_back({n, pow});
            } else{
                mostRight.push_back({st.peek().n, st.peek().pow});
            }
            pow *= 10;
            tmpNum /= 10;
        }
        int idx = mostRight.size() - 1;
        while(pow/10){
            pow /= 10;
            int n = (num % (pow*10)) / pow;
            if (mostRight[idx].n != n){
                num -= n * pow;
                num -= mostRight[idx].n * mostRight[idx].pow;
                num += n * mostRight[idx].pow;
                num += mostRight[idx].n * pow;
                return num;
            }

            idx--;
        }
        return num;
    }
};