Simple O(n) 0ms solution (this is essentially next permutation)


  • 1
    C

    Like the problem of finding next permutation, the key to this problem is to find the first digit[i] which is smaller than digit[i+1] going from right to left. And then we need to find the first smallest digit[j] going from right to left and greater than digit[i].

    Then we just need to swap digit[i] and digit[j], then sort the sub range from [i+1, n) in ascending order.

    If we cannot find such pair of digit[i] and digit[j] we return -1.
    If the newly generated num is greater than INT_MAX we also return -1.

    class Solution {
    public:
        int nextGreaterElement(int n) {
            if (n <= 0) return -1;
            
            string num = to_string(n);
            if (num.size() < 2) return -1;
            
            int lhs = num.size() - 2;
            while (lhs >= 0) {
                if (num[lhs] < num[lhs+1]) break;
                lhs--;
            }
            if (lhs == -1) return -1;
            
            int rhs = num.size() - 1;
            while (rhs > lhs) {
                if (num[rhs] > num[lhs]) break;
                rhs--;
            }
            if (lhs == rhs) return -1;
            
            swap(num[lhs], num[rhs]);
            sort(num.begin()+lhs+1, num.end());
            
            istringstream istr(num);
            long long value;
            istr >> value;
            return value > INT_MAX ? -1 : value;
        }
    };
    

Log in to reply
 

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