LeetCode 738: Monotone Increasing Digits

Problem Restatement

We are given a non-negative integer n.

We need to return the largest integer less than or equal to n whose digits are monotone increasing.

A number has monotone increasing digits when every adjacent digit pair satisfies:

left_digit <= right_digit

For example:

1234 is valid
1119 is valid
332 is not valid

The official constraint is:

0 <= n <= 10^9

Input and Output

Example function shape:

def monotoneIncreasingDigits(n: int) -> int:
    ...

Examples

Example 1

n = 10

10 is not monotone increasing because:

1 > 0

The largest valid number less than or equal to 10 is:

9

Example 2

n = 1234

Every adjacent pair is valid:

1 <= 2 <= 3 <= 4

So the answer is:

1234

Example 3

n = 332

332 is not valid because:

3 <= 3, but 3 > 2

To make the number smaller but as large as possible, reduce the first problematic 3 group and fill the rest with 9.

The answer is:

299

First Thought: Check Numbers Downward

One direct method is to start from n and check each number going downward.

For each number, test whether its digits are monotone increasing.

This works, but it can be far too slow.

If n is close to 10^9, we may need to check many numbers.

We need to modify the digits of n directly.

Key Insight

If the digits are already monotone increasing, n itself is the answer.

If we find a violation:

digits[i - 1] > digits[i]

then the prefix ending at i - 1 is too large.

To get the largest valid number less than n, we should:

1. Decrease some digit on the left by 1.
2. Set every digit after it to 9.

Why 9?

Once the prefix is made smaller, the suffix should be as large as possible. The largest possible suffix is all 9s.

But there is one subtle point.

For:

n = 1332

The violation is 3 > 2.

If we only reduce the second 3, we get:

1322

This is still invalid because:

3 > 2

So we scan from right to left. Whenever a digit is smaller than the digit before it, decrement the previous digit and mark the suffix to become 9.

Algorithm

Convert n to a list of digit characters.

Let:

mark = len(digits)

mark is the first position that should become 9.

Scan from right to left.

For each index i from len(digits) - 1 down to 1:

1. If digits[i] < digits[i - 1]:
   • Decrement digits[i - 1].
   • Set mark = i.

After the scan, set every digit from mark to the end to '9'.

Convert the digit list back to an integer.

Correctness

Whenever digits[i] < digits[i - 1], the number violates the monotone increasing rule at positions i - 1 and i.

Any valid number less than or equal to the original number must reduce some digit at or before i - 1; otherwise, the same invalid prefix would remain. The greedy step reduces digits[i - 1] by exactly 1, which makes the prefix as large as possible while moving below the invalid value.

After the prefix has been reduced, the largest possible suffix is all 9s. Setting the suffix to 9 therefore maximizes the final number among numbers with that reduced prefix.

Scanning from right to left handles cascades correctly. If decrementing one digit creates a new violation with the digit before it, the later leftward scan will detect and fix it. This is why cases like 1332 become 299, not 1329.

After the scan finishes, no adjacent pair before mark violates the monotone rule. All digits from mark onward are 9, so they cannot create a violation with later digits. Therefore the result is monotone increasing.

The algorithm only reduces digits when required by a violation, and each reduction is minimal. The suffix is then maximized with 9s. Therefore the returned number is the largest monotone increasing number less than or equal to n.

Complexity

Let d be the number of digits in n.

Since n <= 10^9, d is at most 10.

Implementation

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        digits = list(str(n))
        mark = len(digits)

        for i in range(len(digits) - 1, 0, -1):
            if digits[i] < digits[i - 1]:
                digits[i - 1] = str(int(digits[i - 1]) - 1)
                mark = i

        for i in range(mark, len(digits)):
            digits[i] = "9"

        return int("".join(digits))

Code Explanation

We convert the number into digits:

digits = list(str(n))

This lets us change individual digits.

The variable mark stores where the suffix of 9s should begin:

mark = len(digits)

If the number is already valid, mark stays at the end, and no digit is changed to 9.

We scan from right to left:

for i in range(len(digits) - 1, 0, -1):

When a violation is found:

if digits[i] < digits[i - 1]:

we decrement the previous digit:

digits[i - 1] = str(int(digits[i - 1]) - 1)

and remember that position i and everything after it should become 9:

mark = i

After all fixes, fill the suffix:

for i in range(mark, len(digits)):
    digits[i] = "9"

Finally, convert back to an integer:

return int("".join(digits))

This automatically handles leading zero cases. For example, 10 becomes "09", and int("09") returns 9.

Testing

def run_tests():
    s = Solution()

    assert s.monotoneIncreasingDigits(10) == 9
    assert s.monotoneIncreasingDigits(1234) == 1234
    assert s.monotoneIncreasingDigits(332) == 299
    assert s.monotoneIncreasingDigits(0) == 0
    assert s.monotoneIncreasingDigits(9) == 9
    assert s.monotoneIncreasingDigits(120) == 119
    assert s.monotoneIncreasingDigits(1332) == 1299
    assert s.monotoneIncreasingDigits(1000) == 999
    assert s.monotoneIncreasingDigits(987654321) == 899999999

    print("all tests passed")

run_tests()