C++ linear time solution using two stacks


  • 1

    create a min and max stack and keep track of the lower and greater elements. If the min stack is empty, array is reversely sorted return same. else pop the max stack until we find a max number index after the min element index. The idea is to replace the earliest smallest number with the latest greater number. (so ignore duplicates)

    class Solution {
    public:
        int maximumSwap(int num) {
            stack<int> minS, maxS;
            string temp = to_string(num);
            int maxi=INT_MIN;
    
            for (int i=temp.size()-1;i>=0;i--){
                int num = temp[i]-'0';
                if (num>maxi){
                    maxi = num;
                    maxS.push(i);
                }else if (num<maxi){
                    minS.push(i);
                }
            }
            
            if (minS.empty())
                return num;
            
            while (maxS.top()<=minS.top()){
                maxS.pop();
            }
            swap(temp[minS.top()], temp[maxS.top()]);
            return stoi(temp);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.