Abstract / Summary

Find the next greater number than the given integer using the same digits.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 35% (500k+ submissions).

Typical patterns to solve this problem:

• Math
• String
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation provides a method to compute the smallest integer that is larger than a given positive integer n and consists of exactly the same digits. If such a number does not exist or exceeds the 32-bit signed integer range, the function returns -1. The algorithm follows a classic “next permutation” approach applied to the decimal representation of the input.

Key Steps

Converting the integer into a digit array

The first phase extracts each decimal digit of n and stores them in a vector in the original order.

vector<int> digits;
while (n > 0)
{
    digits.push_back(n % 10);
    n /= 10;
}
reverse(digits.begin(), digits.end());

The loop isolates the least-significant digit with n % 10, appends it, and then discards it by integer division. After the loop the digits appear reversed, so a call to reverse restores the natural most-significant-to-least-significant order.

Finding the next lexicographic permutation

The standard library routine next_permutation is invoked on the digit vector. It rearranges the sequence into the next greater ordering, if one exists.

if (!next_permutation(digits.begin(), digits.end()))
    return -1;

When the current ordering is already the highest possible (digits sorted descending), next_permutation returns false, and the function signals the absence of a larger number by returning -1.

Restoring the digit order for reconstruction

After obtaining the next permutation, the vector is reversed again. This prepares the digits for a simple pop-back reconstruction that builds the integer from the least significant side.

reverse(digits.begin(), digits.end());

Rebuilding the integer from digits

A 64-bit accumulator is used to avoid overflow while the digits are consumed from the back of the vector.

int64_t result = 0;
while (!digits.empty())
{
    result *= 10;
    result += digits.back();
    digits.pop_back();
}

Each iteration multiplies the current value by ten and adds the next digit, effectively shifting the number left and inserting the new least-significant digit.

Validating the 32-bit range

Before returning, the computed value is compared against the exclusive upper bound of a signed 32-bit integer. If the result is equal to or larger than 2^31, the function returns -1.

if (result >= 2147483648)
    return -1;
return result;

Edge Cases Handled

When the input n is zero, the digit extraction loop produces an empty vector. The subsequent call to next_permutation on an empty range fails, causing the method to return -1. This correctly indicates that no greater permutation exists for the single-digit value zero.

If the digits of n are already arranged in non-increasing order (for example, 4321), next_permutation cannot produce a larger arrangement, and the early return of -1 signals the impossibility of a greater number with the same digits.

The final range check ensures that results exceeding the maximum representable signed 32-bit integer (2147483647) are rejected, even though the intermediate accumulation uses a 64-bit type to avoid overflow during the construction phase.

Performance Optimizations

The algorithm leverages the highly optimized next_permutation from the C++ Standard Library, which operates in linear time relative to the number of digits and performs in-place rearrangement without auxiliary storage.

Reversing the digit vector twice-once after extraction and once after permutation-allows the reconstruction loop to use pop_back, which is an O(1) operation, eliminating the need for index arithmetic or additional temporary containers.

Using a 64-bit accumulator (int64_t) prevents overflow during the digit-by-digit multiplication and addition, avoiding costly checks inside the loop. The final range comparison is performed only once after the entire number has been assembled.

Overall, the method processes the digit sequence with a small constant number of passes and minimal dynamic memory operations, yielding an efficient solution for the problem scope.

Imagine you have a row of wooden number blocks. To start, the computer takes the big number you gave it and breaks it down into individual blocks, putting each one into a little train car. Since the computer likes to peek at the numbers from the back, it turns the line of blocks around so it can organize them more easily.

Now comes the fun part. The computer looks to see if it can rearrange these blocks to make a slightly bigger number. It has a special tool that carefully swaps the blocks until it finds the very next version that is larger than the one you started with. If it discovers that no bigger number can be made, it simply gives up and explains that it is impossible.

If it does find a way to make a bigger number, it collects the blocks again to put them back into their final order. It builds the new number by grabbing each block and sitting it down in its spot, carefully multiplying by ten to make sure each digit lands in the right place, like shifting beads on an abacus. Finally, the computer checks to make sure the brand new number is not too huge to fit inside its box. If the new number fits perfectly, it shows it to you.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java				Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem							Ruby
	fengvyi	C++
	fsq	C++
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	lzl124631x	C++
	ruoru						Rust
	shreymehul					C#
	suxrobGM					C#
	varunu28				Java
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fsq	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality