Monotone Increasing Digits - Solution & Explanation

Problem Overview: Given an integer n, return the largest number less than or equal to n where the digits are in monotone increasing order (each digit is ≤ the next). For example, 1234 is valid, while 332 is not because 3 > 2.

Approach 1: Brute Force Search (O(n * d) time, O(d) space)

The straightforward idea is to iterate downward from n until you find a number whose digits are monotone increasing. For each candidate number, convert it to a string or digit array and check whether every adjacent pair satisfies digit[i] ≤ digit[i+1]. This requires scanning all digits for every number tested. While the digit check costs O(d), the outer loop may run many times, making the total complexity O(n * d) in the worst case. This approach works for small values but quickly becomes impractical for large inputs.

Approach 2: Greedy Digit Adjustment (O(d) time, O(d) space)

The optimal solution uses a greedy strategy on the digit representation of the number. Convert n into an array of digits and scan from left to right to detect the first position where the monotone property breaks (digit[i] < digit[i-1]). When this happens, decrement the previous digit (digit[i-1]--) and mark this position as the point after which all digits should become 9. This ensures the resulting number stays ≤ n while maximizing the suffix.

The tricky part is handling cascading violations. After decrementing a digit, the previous digit may now violate the monotone condition with its left neighbor. Continue moving backward while digit[i] < digit[i-1], decrementing as needed. Once the prefix becomes valid again, fill every digit after the marked position with 9. The result is the largest possible monotone increasing number ≤ n. This algorithm touches each digit at most a few times, giving O(d) time and O(d) space.

This problem is essentially digit manipulation combined with a greedy correction step. Understanding why replacing the suffix with 9s maximizes the result is key: once the prefix is reduced, the best possible remaining digits are the largest allowed values.

Although the logic operates on digits rather than arrays or graphs, it still demonstrates a classic greedy decision process combined with simple math-based reasoning about number structure.

Recommended for interviews: The greedy digit-adjustment approach is the expected solution. Mentioning the brute force method first shows baseline reasoning, but implementing the O(d) greedy fix demonstrates strong understanding of digit manipulation and greedy optimization—exactly what interviewers look for in medium-level problems.