MediumNo. 0556

Next Greater Element III — LeetCode 556 Python Solution

Topics
Math, Two Pointers, String
Reading time
3 min

The problem

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.

Example

Input
n = 12
Output
21

Python solution

PythonSolution
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

Complexity

Time
O(n) (after optional sort O(n log n))
Space · auxiliary
O(1)

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 556. Next Greater Element III is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0564Find the Closest PalindromeHard
0043Multiply StringsMedium
0168Excel Sheet Column TitleEasy
0171Excel Sheet Column NumberEasy
0189Rotate ArrayMedium
0273Integer to English WordsHard

Frequently asked questions

How hard is LeetCode 556. Next Greater Element III?

LeetCode 556. Next Greater Element III is rated Medium on LeetCode.

What is the time complexity of LeetCode 556. Next Greater Element III?

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 556. Next Greater Element III?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 556. Next Greater Element III cover?

LeetCode 556. Next Greater Element III is tagged Math, Two Pointers and String on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.