Abstract / Summary

Given a number, make the smallest change so its digits never decrease from left to right.

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 49% (100k+ submissions).

Typical patterns to solve this problem:

• Greedy
• Math

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 provided implementation solves the “monotone increasing digits” problem by constructing the largest integer not greater than a given n whose decimal digits never decrease when read from left to right. The solution converts the input to a string, then uses a depth-first recursive search to build candidate numbers digit by digit. The search stops as soon as a valid candidate of the same length as the original number is found, and the result is stored in a non-local variable.

Key Steps

Conversion and Result Initialization

s = str(n)
result = 0

The integer n is turned into its string representation s. This representation is used for length checks and lexical comparison. A variable result is prepared to hold the final answer once a suitable candidate is discovered.

Recursive Builder Definition

def deeper(have):
    if have > s:
        return False

    if len(have) == len(s):
        nonlocal result
        result = int(have)
        return True

    last = 0 if not have else int(have[-1])
    for i in range(9, last-1, -1):
        if deeper(have + str(i)):
            return True
    return False

The nested function deeper receives a partial string have that represents the digits chosen so far.

• The first conditional if have > s: aborts any branch where the partially built number already exceeds the original number when compared lexicographically. This prevents unnecessary deeper exploration.
• When the length of have matches the length of s, a complete candidate has been formed. The nonlocal declaration allows the function to assign the integer value of have to the outer result variable, and the function returns True to signal success.
• The variable last captures the most recent digit placed. If no digit has been placed yet, last defaults to 0, allowing any digit from 0 to 9 to start the number.
• The for loop iterates from 9 down to last. By descending, the algorithm prefers larger digits first, which often yields a valid solution early and avoids exploring smaller alternatives.
• The recursive call deeper(have + str(i)) attempts to extend the current prefix with digit i. If the recursive call returns True, the current call also returns True immediately, propagating the success upward.

Invocation and Return

deeper("")
return result

The search starts with an empty prefix. After the recursion finishes, the stored result is returned as the answer.

Edge Cases Handled

When the input n is a single-digit number, the string s has length one. The recursion quickly reaches the length-matching condition, converting the single digit to an integer and returning it.

If n is 0, the initial call receives an empty prefix. The loop still iterates from 9 down to 0, but the lexical check have > s prevents any prefix longer than "0" from being accepted. The algorithm ultimately settles on "0" as the result.

For numbers that contain a decreasing pattern early, such as 321, the lexical guard have > s stops the branch as soon as the prefix exceeds the original number, and the loop’s lower bound last ensures that only non-decreasing digits are appended. This combination guarantees that the algorithm never constructs an invalid decreasing sequence.

When the original number contains trailing zeros, e.g., 1000, the algorithm can generate a candidate like 999 by decreasing the most significant digit and filling the rest with the highest permissible digits, while still respecting the lexical bound. The early termination condition ensures that any prefix that would overshoot 1000 is discarded promptly.

If the input consists entirely of already monotone digits, such as 123456, the recursion follows the exact digits of s because each step can choose the current digit (which is ≥ last). The length-matching condition is reached without any backtracking, and the original number is returned unchanged.

Performance Optimizations

The recursion includes a lexical comparison if have > s: that prunes entire sub-trees the moment the partially built number exceeds the target. This early exit dramatically reduces the number of recursive calls for large inputs with early decreasing patterns.

Iterating the digit choices in descending order (for i in range(9, last-1, -1):) biases the search toward the largest feasible digits. When a valid solution exists, it is often found after exploring only a few branches, allowing the function to return immediately without traversing the full search space.

Storing the answer in a nonlocal variable avoids the overhead of passing result objects through the call stack. The recursion depth is bounded by the number of digits in n, ensuring that the call stack never grows beyond a modest size.

By constructing the candidate as a string and converting it to an integer only at the moment a complete solution is identified, the algorithm minimizes repeated integer parsing and keeps intermediate operations lightweight.

Overall, the combination of lexical pruning, descending digit order, and minimal state mutation yields an efficient exploration of the solution space within the constraints of the problem.

Imagine you are building a tall tower out of colorful number blocks. You want to make sure that as the tower grows, each block is the same size or bigger than the one sitting right below it. If the blocks go from small to big, it looks like a nice, smooth staircase.

This little machine takes a big number and turns it into a secret pile of digits. It starts building a new number one digit at a time by testing different possibilities. It looks at the very last digit that was placed and decides which numbers are allowed to come next. By always picking the biggest possible numbers that keep the staircase growing upwards, it explores every path carefully. It keeps trying different combinations until it finds the tallest possible staircase that still fits within the limit of the original number you gave it. Once it finds the perfect set of blocks that stay in order, it stops searching and sets that winning number aside.

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++			Java
	leetcode.ca	C++	Python		Java			Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	gouthampradhan				Java
	JoshCrozier			JS
	lkwq007		Python
	MacJim	C++
	ruoru					Rust
	suxrobGM						C#
	trung-hn		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
lkwq007	Python
MacJim	C++
ruoru	Rust
suxrobGM	C#
trung-hn	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