0358MediumMathTwo PointersString

Next Lot Stamp

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def next_greater_element(n: int) -> int:

Java

public int nextGreaterElement(int n)

The intended approach

Time O(d) where d is the number of digits of n, so at most 10Space O(d) for the digit list

Read the stamp as a digit list. Walk right to left to the last position whose digit is smaller than the digit just after it; everything to its right is already in descending order and cannot be bumped. Swap that digit with the smallest digit to its right that still exceeds it, then reverse the rest of the tail so the tail reads as low as possible, and reject the result if it passes 2^31 - 1.

Pythonentry point: next_greater_element

def next_greater_element(n):
    # O(d) over the d <= 10 digits: one right-to-left scan for the pivot,
    # one scan for the swap partner, one reversal. O(d) space for the digits.
    d = list(str(n))
    i = len(d) - 2
    while i >= 0 and d[i] >= d[i + 1]:
        i -= 1
    if i < 0:
        return -1
    j = len(d) - 1
    while d[j] <= d[i]:
        j -= 1
    d[i], d[j] = d[j], d[i]
    d[i + 1:] = reversed(d[i + 1:])
    value = int("".join(d))
    if value > 2147483647:
        return -1
    return value

The obvious version

Materialise every distinct permutation of the digit string, keep the ones that read higher than n and still fit the register, and take the minimum.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

from itertools import permutations


def bf_next_greater_element(n):
    best = -1
    for perm in set(permutations(str(n))):
        value = int("".join(perm))
        if value > n and value <= 2147483647:
            if best == -1 or value < best:
                best = value
    return best

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in