DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

2 1

Next Greater Element III

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

SOLUTION:

class Solution:
    def nextGreaterElement(self, n: int) -> int:
        digits = [int(c) for c in str(n)]
        k = len(digits)
        i = k - 1
        while i > 0:
            if digits[i - 1] < digits[i]:
                break
            i -= 1
        if i == 0:
            return -1
        closest = i
        for j in range(i, k):
            if digits[j] > digits[i - 1] and digits[j] - digits[i - 1] <= digits[closest] - digits[i - 1]:
                closest = j
        digits[i - 1], digits[closest] = digits[closest], digits[i - 1]
        op = 0
        for d in range(i):
            op = 10 * op + digits[d]
        for d in range(k - 1, i - 1, -1):
            op = 10 * op + digits[d]
        return op if op <= ((1 << 31) - 1) else -1
Enter fullscreen mode Exit fullscreen mode
πŸ‘‹ While you are here

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Sentry image

See why 4M developers consider Sentry, β€œnot bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

AWS GenAI LIVE!

GenAI LIVE! is a dynamic live-streamed show exploring how AWS and our partners are helping organizations unlock real value with generative AI.

Tune in to the full event

DEV is partnering to bring live events to the community. Join us or dismiss this billboard if you're not interested. ❀️