Next Greater Element III Problem


Description

LeetCode Problem 556.

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:

1
2
Input: n = 12
Output: 21

Example 2:

1
2
Input: n = 21
Output: -1

Constraints:

  • 1 <= n <= 2^31 - 1


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool nextPermutation(string& nums) {
        int i = nums.size()-1;
        while (i > 0 && nums[i-1] >= nums[i]) i--;
        if (i == 0) return false;
        
        int j = nums.size()-1;
        while (j > 0 && nums[j] <= nums[i-1]) j--;
        swap(nums[j], nums[i-1]);
        reverse(nums.begin()+i, nums.end());
        return true;
    }
    
    int nextGreaterElement(int n) {
        string num = to_string(n);
        bool res = nextPermutation(num);
        size_t ans = stoll(num);
        return (!res || ans > INT_MAX) ? -1 : ans;
    }
};




Related Posts

Squares Of A Sorted Array Problem

LeetCode 977. Given an integer array nums sorted in non-decreasing...

Sort Array By Parity Problem

LeetCode 905. Given an integer array nums, move all the...

Sort Array By Parity II Problem

LeetCode 922. Given an array of integers nums, half of...

Shortest Distance To A Character Problem

LeetCode 821. Given a string s and a character c...

Reverse Only Letters Problem

LeetCode 917. Given a string s, reverse the string according...

Push Dominoes Problem

LeetCode 838. There are n dominoes in a line, and...