Next Greater Element III

Intuitionwhy the smallest larger number is a local change followed by the smallest suffix

Numbers with the same digits are ordered exactly like their digit strings when all strings have the same length. So the problem asks for the next lexicographically greater permutation. To stay as small as possible, you must preserve the longest prefix you can and change a digit as far to the right as possible.

Scan from right to left until you find the first position i where s[i] < s[i + 1]. Everything after i is non-increasing, so that suffix is already the largest arrangement of its digits. Swap s[i] with the smallest digit in the suffix that is larger than it, then reverse the suffix. The swap makes the number larger, and the reversal makes the remaining digits as small as possible.

Approach

1. 1Convert n to a string so each digit can be compared and rearranged directly; arithmetic digit extraction would make the permutation logic harder to express and would discard leading-position information.
2. 2Set i to the second-to-last index and move it left while s[i] >= s[i + 1]; this skips the suffix that is already in non-increasing order, and if no index remains, the entire number is the largest permutation.
3. 3Set j to the last index and move it left while s[j] <= s[i]; the suffix is non-increasing, so the first digit found this way is the smallest digit strictly larger than the pivot.
4. 4Swap s[i] and s[j] to create the smallest possible increase at the rightmost changeable position; choosing an earlier position would make the result unnecessarily larger.
5. 5Reverse the range after i because the suffix was non-increasing before the swap and must become increasing after the smallest valid pivot replacement; leaving it descending would produce a larger valid permutation.
6. 6Convert the rearranged string to a 64-bit integer before returning it; this prevents an intermediate overflow, and comparing with INT_MAX enforces the required 32-bit result limit.

Complexitythe input has at most ten digits, but the permutation argument is general

Annotated solutionC++ · next-permutation structure · complete judge-ready implementation

#include <algorithm>
#include <climits>
#include <string>

using namespace std;

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        int len = static_cast<int>(s.size());
        int i = len - 2;

        while (i >= 0 && s[i] >= s[i + 1]) {
            --i;
        }

        if (i < 0) {
            return -1;
        }

        int j = len - 1;
        while (s[j] <= s[i]) {
            --j;
        }

        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());

        long long result = stoll(s);
        return result > INT_MAX ? -1 : static_cast<int>(result);
    }
};

The two scans rely on the suffix being non-increasing. Because i is the first valid position found while moving from the right, every position after i belongs to that suffix. Its digits are already arranged from large to small, so after swapping in the smallest larger digit, reversing the suffix is enough to obtain increasing order without another search or sort.

Common mistakestwo wrong shapes that often look plausible