LeetCode 738 - Monotone Increasing Digits

The problem asks us to find the largest integer less than or equal to a given number n, such that its digits are monotone increasing. A number has monotone increasing digits when every digit is less than or equal to the digit that comes after it.

leetcodemediummathgreedy

LeetCode Problem 738

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to find the largest integer less than or equal to a given number n, such that its digits are monotone increasing.

A number has monotone increasing digits when every digit is less than or equal to the digit that comes after it. For example:

  • 1234 is monotone increasing because 1 <= 2 <= 3 <= 4
  • 11239 is also monotone increasing because equal adjacent digits are allowed
  • 332 is not monotone increasing because 3 > 2

The input is a single integer n, where:

$0 \le n \le 10^9$

This constraint tells us the number has at most 10 digits, so the input size is very small. However, we still want an efficient algorithm rather than checking every number one by one.

The output should be the largest number satisfying two conditions:

  1. It is less than or equal to n
  2. Its digits are monotone increasing

The key challenge is that changing one digit can force changes to later digits as well. For example:

  • 332

  • The violation occurs because 3 > 2

  • Reducing the second 3 to 2 gives 322

  • But 322 still violates monotonicity because 3 > 2

  • The correct answer is 299

This cascading effect is the core difficulty of the problem.

Several edge cases are important:

  • Numbers already monotone increasing, like 1234
  • Numbers with repeated digits, like 111
  • Numbers where decreasing one digit creates a new violation to the left
  • Numbers containing zeros, like 10
  • Single digit numbers, which are always valid

The problem guarantees that the input is a non-negative integer, so we never need to handle invalid input types or negative values.

Approaches

Brute Force Approach

The most straightforward approach is to start from n and repeatedly decrease the number until we find one whose digits are monotone increasing.

For each candidate number:

  1. Convert it to a string
  2. Check whether every adjacent pair satisfies digit[i] <= digit[i+1]
  3. If valid, return it
  4. Otherwise decrement and continue

This approach is correct because we examine numbers from largest to smallest, so the first valid number encountered must be the answer.

However, this can be extremely slow. Consider a large input where many consecutive numbers are invalid. In the worst case, we may check a huge range of values.

For example:

  • 1000000000
  • We may need many decrements before reaching a valid monotone number

Even though the input size in digits is small, the numeric range is large enough that brute force is not practical.

Optimal Greedy Approach

The key observation is that when a digit violates monotonicity, we should reduce the offending digit and make all digits to its right as large as possible.

Suppose we have:

332

At the point where 3 > 2, we know the second 3 must decrease. If we reduce it to 2, the largest possible suffix becomes all 9s:

329

But now the first 3 is greater than 2, so we must repeat:

299

This suggests a greedy strategy:

  • Scan digits from right to left

  • Whenever a digit is greater than the digit after it:

  • Decrease the current digit by 1

  • Set all following digits to 9

Why does this work?

Because once we reduce a digit, the best way to maximize the resulting number is to make every later digit as large as possible while preserving monotonicity. Since 9 is the largest digit, filling the suffix with 9s produces the largest valid number.

The right-to-left scan is important because decreasing one digit can create a new violation with the digit before it.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * d) O(d) Checks every number downward, where d is digit count
Optimal O(d) O(d) Greedy digit adjustment, extremely efficient

Since d <= 10, the optimal solution effectively runs in constant time.

Algorithm Walkthrough

  1. Convert the integer into a list of digits.

We use a mutable structure because digits may need modification during processing. 2. Start scanning from right to left.

We compare each digit with the digit immediately after it. If the current digit is greater than the next digit, monotonicity is violated. 3. When a violation is found, decrease the current digit by 1.

For example:

332

At index 1:

3 > 2

So we decrease the second digit:

322
  1. Record the position where digits to the right should become 9.

After reducing a digit, we want the remaining suffix to be as large as possible while staying valid.

So:

322 -> 299
  1. Continue scanning leftward.

Decreasing one digit may create another violation.

Example:

299

Now the first 3 is greater than 2, so we must reduce again. 6. After the scan completes, replace all digits after the recorded position with 9.

This maximizes the final value. 7. Convert the digit list back into an integer and return it.

Why it works

The algorithm maintains the invariant that whenever a violation is fixed, the resulting prefix becomes the largest possible valid prefix smaller than the original number. Setting the suffix to 9s guarantees the maximum possible number under that prefix. Because we process from right to left, any cascading violations are also corrected. Therefore the final number is both monotone increasing and as large as possible.

Python Solution

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

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

        for i in range(marker, len(digits)):
            digits[i] = '9'

        return int("".join(digits))

The implementation begins by converting the number into a list of string digits. This allows direct modification of individual positions.

The variable marker stores the first index where digits to the right should eventually become 9. Initially, it is set to the end of the array because no violations have been found yet.

The loop scans from right to left. Whenever a digit is larger than the digit after it, monotonicity is violated. The current digit is decreased by one, and the marker is updated.

The right-to-left direction is essential because decreasing a digit may create a new violation with the digit before it.

After all violations are fixed, every digit from marker onward is replaced with 9. This maximizes the resulting number while ensuring it remains less than or equal to the original input.

Finally, the digit list is joined back into a string and converted into an integer.

Go Solution

func monotoneIncreasingDigits(n int) int {
    digits := []byte(fmt.Sprintf("%d", n))
    marker := len(digits)

    for i := len(digits) - 1; i > 0; i-- {
        if digits[i-1] > digits[i] {
            digits[i-1]--
            marker = i
        }
    }

    for i := marker; i < len(digits); i++ {
        digits[i] = '9'
    }

    result := 0
    for _, ch := range digits {
        result = result*10 + int(ch-'0')
    }

    return result
}

The Go implementation follows the same logic as the Python version.

A byte slice is used because strings in Go are immutable. Each digit is stored as its ASCII byte representation, making in-place updates efficient.

The decrement operation is particularly simple in Go because digit characters are sequential in ASCII:

digits[i-1]--

After modification, the digits are reconstructed into an integer manually rather than using parsing utilities.

Unlike Python, Go requires explicit integer reconstruction and does not provide direct mutable string manipulation.

Worked Examples

Example 1

Input:

n = 10

Initial digits:

Index Digit
0 1
1 0

Right-to-left scan:

i Comparison Action Digits
1 1 > 0 Decrease 1 to 0, marker = 1 00

Replace digits from marker onward with 9:

Digits
09

Final result:

9

Example 2

Input:

n = 1234

Initial digits:

Index Digit
0 1
1 2
2 3
3 4

Right-to-left scan:

i Comparison Action
3 3 <= 4 None
2 2 <= 3 None
1 1 <= 2 None

No violations occur.

Final result:

1234

Example 3

Input:

n = 332

Initial digits:

Index Digit
0 3
1 3
2 2

Right-to-left scan:

i Comparison Action Digits
2 3 > 2 Decrease second 3 to 2, marker = 2 322
1 3 > 2 Decrease first 3 to 2, marker = 1 222

Replace digits from marker onward with 9:

Digits
299

Final result:

299

Complexity Analysis

Measure Complexity Explanation
Time O(d) Single pass through the digits
Space O(d) Digit array storage

Here, d represents the number of digits in the input number. Since the constraint limits n to at most 10^9, we have at most 10 digits. Therefore the algorithm is extremely efficient in practice and effectively constant time.

Test Cases

sol = Solution()

assert sol.monotoneIncreasingDigits(10) == 9          # basic decreasing case
assert sol.monotoneIncreasingDigits(1234) == 1234     # already monotone
assert sol.monotoneIncreasingDigits(332) == 299       # cascading violation
assert sol.monotoneIncreasingDigits(0) == 0           # minimum input
assert sol.monotoneIncreasingDigits(9) == 9           # single digit
assert sol.monotoneIncreasingDigits(11) == 11         # repeated equal digits
assert sol.monotoneIncreasingDigits(120) == 119       # middle digit violation
assert sol.monotoneIncreasingDigits(1000) == 999      # leading reduction
assert sol.monotoneIncreasingDigits(111110) == 99999  # multiple cascading reductions
assert sol.monotoneIncreasingDigits(135679) == 135679 # strictly increasing digits
assert sol.monotoneIncreasingDigits(987654321) == 899999999 # large decreasing number
assert sol.monotoneIncreasingDigits(101) == 99        # zero in middle
assert sol.monotoneIncreasingDigits(123454321) == 123449999 # late violation

Test Summary

Test Why
10 Smallest non-monotone two-digit number
1234 Already valid increasing sequence
332 Cascading digit correction
0 Lower boundary
9 Single digit input
11 Equal adjacent digits
120 Internal monotonicity break
1000 Leading digit reduction
111110 Multiple repeated digits before violation
135679 Strictly increasing input
987654321 Large descending number
101 Zero causes adjustment
123454321 Violation deep in suffix

Edge Cases

One important edge case is numbers that are already monotone increasing. For example, 1234 should remain unchanged. A careless implementation might modify digits unnecessarily or incorrectly set trailing digits to 9. This implementation avoids that because the marker only changes when a violation is detected.

Another important case is cascading violations. Consider 332. Reducing the second digit creates a new violation with the digit before it. A left-to-right approach often fails here because it cannot revisit earlier digits easily. The right-to-left scan naturally handles cascading updates correctly.

A third important edge case is numbers containing zeros after a larger digit, such as 10 or 1000. Reducing the leading digit may produce leading zeros internally. For example:

10 -> 09

The implementation handles this safely because converting the final string back to an integer automatically removes leading zeros.

A fourth subtle edge case is repeated digits before a violation, such as 111110. When the final 0 is encountered, multiple earlier digits may need adjustment indirectly. The greedy propagation process correctly transforms the number into 99999, which is the largest valid answer.