Show problems as
Classic problem #556MediumMathTwo PointersString

Next Greater Element III

Real-world version: Next Lot Stamp
Tracked in this browser only
Read Next Greater Element III on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rotary engraver marks every production lot with a numeric stamp. When a lot is re-run the shop leaves the digit wheels loaded exactly as they are, so the replacement stamp has to be built from the digits already on the machine: every wheel is used, none is added and none is dropped. To keep the lots in order the replacement must also read higher than the stamp it replaces.

Given the current stamp n, return the lowest stamp that can be assembled by rearranging the digits of n and that reads strictly higher than n.

The stamp register is a signed 32-bit field, so it cannot hold a value above 2^31 - 1. Return -1 if no rearrangement of the digits reads higher than n, and also return -1 if the lowest such rearrangement is too large for the register.

Examples

Example 1

Input
n = 2761
Output
6127

6127 uses the digits 2, 7, 6 and 1 once each, the same wheels as 2761, and it reads higher than 2761.

Example 2

Input
n = 90
Output
-1

The two wheels can only be arranged as 90 or as 09, and 09 reads as 9, which is below 90.

Example 3

Input
n = 1993
Output
3199

3199 holds one 1, two 9s and one 3, matching the wheels of 1993, and it reads higher than 1993.

Example 4

Input
n = 1999999999
Output
-1

Rearrangements above 1999999999 exist, and 9199999999 is the lowest of them, but that is past 2^31 - 1 so the register cannot hold it.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def next_greater_element(n: int) -> int:
Java
public int nextGreaterElement(int n)

More on the same topics