Next Arrangement of Digits
MediumMath & Geometry
Problem
A lock shows a positive integer n. You may only rearrange its digits. Return the smallest integer strictly greater than n that uses exactly the same digits (the same number of each digit).
If no rearrangement is larger, return -1.
Example 1
- Input:
- n = 1243
- Output:
- 1324
Bumping the 2 to the next larger available digit, 3, and arranging the rest in ascending order gives the smallest larger number.
Example 2
- Input:
- n = 4321
- Output:
- -1
The digits are already in descending order.
Example 3
- Input:
- n = 1020
- Output:
- 1200
Constraints
- 1 ≤ n < 10^15
Hint
Show the first hint
To get the next larger number, change as far to the right as possible.
Walkthrough
How to approach it
01Clarify before coding
- Can the answer have leading zeros? No: the result is larger with the same length, so its first digit is at least the original first digit.
- Repeated digits? Yes, like 115 → 151; the comparisons must use strict and non-strict inequality carefully.
- Does the answer fit? It has the same number of digits as n, so it stays below 10^15.
02Brute force
Generate every permutation of the digits, keep those greater than n, and take the minimum.
Cost: O(d! · d) for d digits: 15! is about 1.3 · 10^12 permutations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.