Monotone Increasing Digits: Greedy Digit Manipulation

Here is a fun one that looks like it should be simple but has a subtle twist. LeetCode 738: Monotone Increasing Digits gives you a number and asks you to find the largest number that is at most n where every digit is less than or equal to the next. The greedy insight is clean once you see it, but getting the details right takes careful thought.

The problem

Given a non-negative integer n, find the largest number that is less than or equal to n with monotone increasing digits. A number has monotone increasing digits if each pair of adjacent digits satisfies d[i] <= d[i+1], reading left to right. For example, 123, 1199, and 2999 all have monotone increasing digits, while 332 and 541 do not.

If the input already has monotone increasing digits, return it as-is. Otherwise, you need to find the largest valid number below it.

The approach

The key insight is a greedy right-to-left scan. Convert the number to a list of digit characters, then walk backward through the list. Whenever you find a digit that is strictly greater than the one to its right, you have a "drop" that violates the monotone property. When you find a drop, decrement the left digit by one and record the position. After the scan, fill every digit from the recorded position onward with '9'. This gives you the largest possible monotone increasing number that fits under the original.

Why does this work? Decrementing a digit and filling everything after it with 9s is the largest number you can produce with that prefix. And by scanning right to left, you handle cascading drops naturally. If decrementing one digit creates a new drop with the digit before it, the next iteration of the loop catches it.

def monotone_increasing_digits(n: int) -> int:
    digits = list(str(n))
    mark = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i - 1] > digits[i]:
            mark = i
            digits[i - 1] = str(int(digits[i - 1]) - 1)
    for i in range(mark, len(digits)):
        digits[i] = '9'
    return int(''.join(digits))

Step-by-step walkthrough

Let's trace through n = 332 to see exactly how the algorithm finds 299. At each step, watch which digits get compared, where the drop is detected, and how the mark variable tracks where to start filling 9s.

The algorithm makes a single pass through the digits from right to left, then a second pass to fill in the 9s. The two-pass structure keeps the logic clean and avoids any backtracking.

Complexity analysis

Time: The algorithm makes two linear passes through the digit array. The first pass scans right to left looking for drops and the second pass fills 9s from the mark position onward. Both are O(d) where d is the number of digits in n.

Space: The digit array takes O(d) space. No other data structures are needed beyond a single integer variable (mark) to track the fill position.

The building blocks

Greedy right-to-left scanning

The core technique here is scanning a digit array from right to left to detect violations and fix them greedily. This pattern shows up whenever you need to enforce some ordering property on a sequence and want the "largest" or "smallest" result.

The reason right-to-left works better than left-to-right for this problem is cascading corrections. If you scan left to right and find that digits[2] > digits[3], you might decrement digits[2]. But now digits[1] might be greater than the new digits[2], creating a fresh violation behind you. You would need to rescan, turning a linear algorithm into a quadratic one.

Scanning right to left avoids this entirely. When you decrement digits[i-1] because of a drop, the very next iteration checks whether digits[i-2] > digits[i-1]. If the decrement caused a new violation, you catch it immediately. One pass handles everything.

Digit array conversion

Converting an integer to a list of character digits with list(str(n)) is a common Python pattern for problems that require per-digit manipulation. It gives you random access to individual digits and lets you modify them in place. When you are done, int(''.join(digits)) converts back. This conversion pair handles leading zeros automatically because int("0299") returns 299.

Edge cases

Already monotone increasing. If the input is already valid (like 1234 or 1111), the scan finds no drops, mark stays at len(digits), no 9s get filled, and the original number is returned unchanged.

Single digit. Any single-digit number from 0 to 9 is trivially monotone increasing. The loop body never executes because there are no adjacent pairs to compare.

All same digits. A number like 3333 has no drops (equal digits satisfy the <= condition). The algorithm returns it as-is.

Cascading drops. A number like 332 or 10 demonstrates how a single drop can cascade leftward. In 332, the drop at position 1-2 triggers a decrement, and then the new digits at position 0-1 trigger another decrement. The algorithm handles this in a single right-to-left pass.

From understanding to recall

The greedy right-to-left scan with a mark variable is the entire algorithm here. It is short, elegant, and easy to understand when you read it. But reconstructing it from scratch means remembering three things: scan right to left, decrement and update the mark on each drop, then fill 9s from the mark onward. Those are recall details, not conceptual challenges. Spaced repetition turns this algorithm from something you can follow into something you can write from memory in under a minute.

Related posts

• Plus One - Digit array manipulation with carry propagation
• Remove K Digits - Another greedy digit removal problem
• Next Permutation - Scanning digits to find the right swap point