Code 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))
      

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string digits = to_string(n);
        int mark = digits.size();
        for (int i = digits.size() - 1; i > 0; --i) {
            if (digits[i] < digits[i - 1]) {
                digits[i - 1]--;
                mark = i;
            }
        }
        for (int i = mark; i < digits.size(); ++i) {
            digits[i] = '9';
        }
        return stoi(digits);
    }
};
      

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int mark = digits.length;
        for (int i = digits.length - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                digits[i - 1]--;
                mark = i;
            }
        }
        for (int i = mark; i < digits.length; i++) {
            digits[i] = '9';
        }
        return Integer.parseInt(new String(digits));
    }
}
      

var monotoneIncreasingDigits = function(n) {
    let digits = n.toString().split('');
    let mark = digits.length;
    for (let i = digits.length - 1; i > 0; i--) {
        if (digits[i] < digits[i - 1]) {
            digits[i - 1] = (parseInt(digits[i - 1]) - 1).toString();
            mark = i;
        }
    }
    for (let i = mark; i < digits.length; i++) {
        digits[i] = '9';
    }
    return parseInt(digits.join(''));
};
      

Problem Description

You are given a non-negative integer n. Your task is to find the largest number less than or equal to n such that its digits are in monotone increasing order, meaning each digit is less than or equal to the digit that follows it.

For example, if n = 332, the answer should be 299, because 299 is the largest number less than or equal to 332 whose digits are in increasing order.

Constraints:

• 0 ≤ n ≤ 10⁹
• There is only one valid solution for each input.
• Digits must be used in their original order; you cannot rearrange them.

Thought Process

At first, you might consider checking every number from n down to 0 to see if its digits are monotone increasing. However, this would be extremely inefficient for large values of n.

Instead, let's analyze what it means for a number to have monotone increasing digits. For any given digit, as long as it is not greater than the digit to its right, the number is still valid. But if a digit is greater than the one after it, we need to "fix" this to maintain the monotone property.

The key insight is that when we find a digit that breaks the rule (i.e., it's larger than the next digit), we should decrease this digit by 1 and set all digits to its right to 9. This ensures we get the largest possible number less than or equal to n that is monotone increasing.

Solution Approach

• Convert the number to a list of digits: This makes it easier to manipulate individual digits.
• Scan from right to left: Starting from the least significant digit, check if the current digit is less than the digit before it.
• Fix violations: If a digit is less than the one before it, decrement the previous digit by 1 and remember the position. All digits to the right of this position will eventually be set to 9.
• Set trailing digits: After the scan, set all digits to the right of the marked position to 9. This ensures the number is as large as possible while still being monotone increasing.
• Convert back to integer: Join the digits and convert to an integer to return the result.

This approach efficiently finds the correct answer in a single pass from right to left, and another to fill the trailing digits.

Example Walkthrough

Let's walk through the example where n = 332:

• Convert to digits: ['3', '3', '2']
• Start from right: compare '2' and '3' (positions 2 and 1). Since '2' < '3', decrement the '3' at position 1 to '2', and record position 2 as the mark.
• Now digits: ['3', '2', '2']
• Compare '2' and '3' (positions 1 and 0). Again, '2' < '3', so decrement the '3' at position 0 to '2', and record position 1 as the mark.
• Now digits: ['2', '2', '2']
• Set all digits after position 1 to '9': ['2', '2', '9']
• Set all digits after position 0 to '9': ['2', '9', '9']
• Final answer: 299

At each step, we ensure the digits to the left are not greater than those to the right, and by setting trailing digits to 9, we keep the result as large as possible.

Time and Space Complexity

• Brute-force approach: Checking every number from n down to 0 would take O(n * d), where d is the number of digits. This is infeasible for large n.
• Optimized approach: We process each digit at most twice (once for the scan, once for filling 9s), so the time complexity is O(d), where d is the number of digits (at most 10 for n ≤ 10^9).
• Space complexity: O(d) for storing the digits as a list or string.

Summary

The problem asks for the largest number less than or equal to n with digits in monotone increasing order. By scanning the digits from right to left and fixing any violations by decrementing and setting trailing digits to 9, we can efficiently find the answer in linear time relative to the number of digits. The solution is elegant because it leverages the structure of the problem and avoids brute-force enumeration.