Skip to content

556. Next Greater Element III

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 <= 231 - 1

Solutions

Solution 1

Thinking

We need the next greater integer that is a permutation of \(n\)'s digits. That is exactly the next-permutation algorithm.

Find the rightmost descent \(i\), then the rightmost \(j\) that is larger than \(cs[i]\), swap, and reverse the suffix into increasing order. No descent means \(n\) is already maximal. Overflow past \(32\)-bit also yields \(-1\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def nextGreaterElement(self, n: int) -> int:
        cs = list(str(n))
        n = len(cs)
        i, j = n - 2, n - 1
        while i >= 0 and cs[i] >= cs[i + 1]:
            i -= 1
        if i < 0:
            return -1
        while cs[i] >= cs[j]:
            j -= 1
        cs[i], cs[j] = cs[j], cs[i]
        cs[i + 1 :] = cs[i + 1 :][::-1]
        ans = int(''.join(cs))
        return -1 if ans > 2**31 - 1 else ans

 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
class Solution {
    public int nextGreaterElement(int n) {
        char[] cs = String.valueOf(n).toCharArray();
        n = cs.length;
        int i = n - 2, j = n - 1;
        for (; i >= 0 && cs[i] >= cs[i + 1]; --i)
            ;
        if (i < 0) {
            return -1;
        }
        for (; cs[i] >= cs[j]; --j)
            ;
        swap(cs, i, j);
        reverse(cs, i + 1, n - 1);
        long ans = Long.parseLong(String.valueOf(cs));
        return ans > Integer.MAX_VALUE ? -1 : (int) ans;
    }

    private void swap(char[] cs, int i, int j) {
        char t = cs[i];
        cs[i] = cs[j];
        cs[j] = t;
    }

    private void reverse(char[] cs, int i, int j) {
        for (; i < j; ++i, --j) {
            swap(cs, i, j);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);
        n = s.size();
        int i = n - 2, j = n - 1;
        for (; i >= 0 && s[i] >= s[i + 1]; --i)
            ;
        if (i < 0) return -1;
        for (; s[i] >= s[j]; --j)
            ;
        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());
        long ans = stol(s);
        return ans > INT_MAX ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func nextGreaterElement(n int) int {
    s := []byte(strconv.Itoa(n))
    n = len(s)
    i, j := n-2, n-1
    for ; i >= 0 && s[i] >= s[i+1]; i-- {
    }
    if i < 0 {
        return -1
    }
    for ; j >= 0 && s[i] >= s[j]; j-- {
    }
    s[i], s[j] = s[j], s[i]
    for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
    ans, _ := strconv.Atoi(string(s))
    if ans > math.MaxInt32 {
        return -1
    }
    return ans
}

Comments