Next Greater Element Iv - Leetcode Solution

The Next Greater Element IV problem on leetcode asks us to find the next greater permutation of a given integer. In other words, given a positive integer in the form of a string, we need to find the smallest number greater than it, that can be formed by rearranging its digits.

For example, if the input integer is "1234", the next greater permutation would be "1243".

To solve this problem, we can follow the following steps:

1. Convert the integer given as a string into a list of integers. This will make it easier to manipulate its digits.

2. Traverse the list from right to left to find the first digit that is smaller than the digit to its right. This digit is known as the pivot. For example, in the integer "1234", the pivot would be "3" since it is smaller than "4".

3. If a pivot is found, then we can iterate over the list again from right to left and find the first digit that is greater than the pivot. This digit will then be swapped with the pivot.

4. Now we have a new pivot, which is the digit immediately to the right of the old pivot. We can sort all the digits to the right of the new pivot in ascending order to obtain the next greater permutation.

5. If no pivot is found in step 2, then the given integer is already the largest possible permutation, and we can return the smallest possible permutation, which is formed by sorting its digits in ascending order.

Here's the Python code that implements the above algorithm:

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        # convert the integer to a list of digits
        digits = list(str(n))

        # find the pivot
        pivot_idx = len(digits) - 2
        while pivot_idx >= 0 and digits[pivot_idx] >= digits[pivot_idx+1]:
            pivot_idx -= 1

        # if no pivot is found, return -1
        if pivot_idx == -1:
            return -1

        # find the next greater digit to the right of the pivot
        for i in range(len(digits)-1, pivot_idx, -1):
            if digits[i] > digits[pivot_idx]:
                digits[i], digits[pivot_idx] = digits[pivot_idx], digits[i]
                break

        # sort the digits to the right of the pivot in ascending order
        left, right = pivot_idx+1, len(digits)-1
        while left < right:
            digits[left], digits[right] = digits[right], digits[left]
            left += 1
            right -= 1

        # convert the list of digits back to an integer and return it
        new_num = int("".join(digits))
        return new_num if new_num < 2**31 else -1

The time complexity of this algorithm is O(n), where n is the number of digits in the input integer. The worst-case space complexity is also O(n), since we are storing the digits in a list.

1