Skip to content

Next Greater Element III⚓︎

Link

Description⚓︎

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^31 - 1

Solution⚓︎

STL Solution⚓︎

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int nextGreaterElement(int n) {
        string digits = to_string(n);
        next_permutation(digits.begin(), digits.end());
        long long res = stoll(digits);
        return (res > INT_MAX || res <= n) ? -1 : res;
    }
};

Self-Implemented Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int nextGreaterElement(int n) {
        string str = to_string(n);
        int len = str.length();

        int index = -1;
        for (int i = len - 1; i >= 0; i--) {
            if (str[i] < str[i + 1]) {
                index = i;
                break;
            }
        }

        if (index == -1) {
            return -1;
        }

        for (int i = len; i >= index; i--) {
            if (str[i] > str[index]) {
                swap(str[i], str[index]);
                break;
            }
        }

        reverse(str.begin() + index + 1, str.end());

        long long res = stoll(str);
        return res > INT_MAX ? -1 : res;
    }
};