C++ solution focusing on next permutation with elegant overflow detection


  • 0
    R

    string to int, int to string is not the focus here.
    I use standard library to do this.

        int nextGreaterElement(int n) {
            string s = to_string(n);
            
            // 1. find from right to left the first number less than it's right neighbor
            int left = s.size() - 1;
            while(left >=0 && s[left] >= s[left+1]) --left;
            
            if(left < 0) return -1;
            
            // 2. find from right to left the first number greater than the char at position left 
            int right = s.size() - 1;
            while(s[right] <= s[left]) --right;
            
            // 3. swap these 2 number
            swap(s[left], s[right]);
            
            // 4. reverse [left+1, end]
            reverse(s.begin()+left+1, s.end());
            
            // 5. convert to int and check overflow
            int num;
            try {
                num = stoi(s);
            } catch (out_of_range& e) {
                num = -1;
            }
            
            return num;
        }
    

Log in to reply
 

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