269. Next Greater Element III

The next larger number with the same digits is exactly the 'next permutation' of the digit string. Find the rightmost digit smaller than its neighbour (the pivot), swap it with the smallest larger digit to its right, then reverse the suffix to make it as small as possible.

It's the next permutation

Treat n as a string of digits. The smallest number greater than n using the same digits is the next lexicographic permutation of those digits.

The three steps

1. Find the pivot. Scan from the right for the first index i with d[i] < d[i+1]. Everything to the right of i is non-increasing (already the largest arrangement). If no such i exists, the digits are fully descending — no larger number → return -1.
2. Swap. Find the smallest digit to the right of i that is still larger than d[i] (scan from the right until d[j] > d[i]), and swap d[i] and d[j].
3. Reverse the suffix. The part after i is still descending; reversing it makes it ascending — the smallest possible tail.

Finally, check the result fits in a 32-bit signed integer; if not, return -1.

Worked example

n = 12443322 → digits 1 2 4 4 3 3 2 2.

1. Pivot: scanning right, d[1]=2 < d[2]=4 → i = 1.
2. Swap: smallest digit right of i greater than 2 is 3 (rightmost such) → swap → 1 3 4 4 3 2 2 2.
3. Reverse suffix after index 1 (4 4 3 2 2 2 → 2 2 2 3 4 4) → 1 3 2 2 2 3 4 4.

Result: 13222344.

Complexity

• Time: O(k) where k is the number of digits.
• Space: O(k) for the digit array.

class Solution {
    public int nextGreaterElement(int n) {
        char[] d = String.valueOf(n).toCharArray();
        int i = d.length - 2;
        while (i >= 0 && d[i] >= d[i + 1]) i--;
        if (i < 0) return -1;
        int j = d.length - 1;
        while (d[j] <= d[i]) j--;
        char t = d[i]; d[i] = d[j]; d[j] = t;
        int l = i + 1, r = d.length - 1;
        while (l < r) { char tmp = d[l]; d[l] = d[r]; d[r] = tmp; l++; r--; }
        long val = Long.parseLong(new String(d));
        return val <= Integer.MAX_VALUE ? (int) val : -1;
    }
}