## 556. Next Greater Element III

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

Example 1:

```Input: 12
Output: 21
```

Example 2:

```Input: 21
Output: -1
```

b'
\n\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

To solve the given problem, we treat the given number as a string, . In this approach, we find out every possible permutation of list formed by the elements of the string formed. We form a list of strings, , containing all the permutations possible. Then, we sort the given to find out the permutation which is just larger than the given one. But this one will be a very naive approach, since it requires us to find out every possible permutation which will take really long time.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . A total of permutations are possible for a number consisting of digits.

\n
• \n
• \n

Space complexity : . A total of permutations are possible for a number consisting of digits, with each permutation consisting of digits.

\n
• \n
\n
\n

#### Approach #2 Linear Solution [Accepted]

\n

Algorithm

\n

In this case as well, we consider the given number as a character array .\nFirst, we observe that for any given sequence that is in descending order, no next larger permutation is possible.\n For example, no next permutation is possible for the following array:\n `[9, 5, 4, 3, 1]`

\n

We need to find the first pair of two successive numbers and , from the right, which satisfy\n . Now, no rearrangements to the right of can create a larger permutation since that subarray consists of numbers in descending order.\n Thus, we need to rearrange the numbers to the right of including itself.

\n

Now, what kind of rearrangement will produce the next larger number? We want to create the permutation just larger than the current one. Therefore, we need to replace the number with the number which is just larger than itself among the numbers lying to its right section, say .

\n \n

We swap the numbers and . We now have the correct number at index . But still the current permutation isn\'t the permutation\n that we are looking for. We need the smallest permutation that can be formed by using the numbers only to the right of . Therefore, we need to place those\n numbers in ascending order to get their smallest permutation.

\n

But, recall that while scanning the numbers from the right, we simply kept decrementing the index\n until we found the pair and where, . Thus, all numbers to the right of were already sorted in descending order.\n Furthermore, swapping and didn\'t change that order.\n Therefore, we simply need to reverse the numbers following to get the next smallest lexicographic permutation.

\n

The following animation will make things clearer:

\n\n

!?!../Documents/556_Next_Greater_Element_III.json!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . In worst case, only two scans of the whole array are needed. Here, refers to the number of digits in the given number.

\n
• \n
• \n

Space complexity : . An array of size is used, where is the number of digits in the given number.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'