#556 Next Greater Element III - Solution

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.

Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.

Example 1:

Input: n = 12
Output: 21

Example 2:

Input: n = 21
Output: -1

Constraints:

1 <= n <= 2³¹ - 1

Approach	Time Complexity	Space Complexity
Next Permutation on Digits	O(d)	O(d)

Solutions (12)

Approach 1: Next Permutation

This approach uses the concept of finding the next permutation of the digits of the number. We traverse the digits from right to left to find the first digit that is smaller than the digit next to it. Once found, we swap it with the smallest larger digit on its right and then reverse the sequence following the swapped digit.

Time Complexity: O(n log n) (due to sorting in worst case)
Space Complexity: O(1) (in-place swap and conversion)

C C++Java Python C#JavaScript

1function nextGreaterElement(n) {
2    let digits = n.toString().split('');
3    let i = digits.length - 2;

Explanation

The JavaScript solution follows a similar pattern with array manipulations to find the next greater permutation. The method leverages array methods to reverse portions of the sequence and joins arrays to form the final result.

Approach 2: Mathematical Permutation Logic

This approach entails understanding mathematical permutation generation principles. First, identify the point where the digits stop increasing when moving left-to-right, then swap it. Finally, regenerate that segment to form the smallest sequential increase.

Time Complexity: O(n^2) (as it checks for minimum swap position for small digits segment)
Space Complexity: O(n) (array storage)

C C++Java Python C#JavaScript

1using System.Linq;

public class Solution {
    public int NextGreaterElement(int n) {
        char[] digits = n.ToString().ToCharArray();
        int i = digits.Length - 2;
        while (i >= 0 && digits[i] >= digits[i + 1]) i--;
        if (i < 0) return -1;
        int j = digits.Length - 1;
        while (digits[j] <= digits[i]) j--;
        char temp = digits[i];
        digits[i] = digits[j];
        digits[j] = temp;
        Array.Sort(digits, i + 1, digits.Length - i - 1);
        try {
            return int.Parse(new string(digits));
        } catch (OverflowException) {
            return -1;
        }
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.NextGreaterElement(12));
    }
}