An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.
Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.
Example 1:
Input: n = 10 Output: 9
Example 2:
Input: n = 1234 Output: 1234
Example 3:
Input: n = 332 Output: 299
Constraints:
0 <= n <= 109The goal in Monotone Increasing Digits is to find the largest integer less than or equal to n such that its digits are in non‑decreasing order (each digit is greater than or equal to the previous one). A common strategy is a greedy approach based on digit inspection.
Convert the number into a sequence of digits (using a string or array). Traverse the digits from left to right and detect where the monotonic property breaks, meaning digit[i] < digit[i-1]. When this happens, decrease the previous digit and mark the position where all subsequent digits should be set to 9 to maximize the resulting number while preserving the monotone condition.
Sometimes decrementing a digit can create a new violation with earlier digits, so the algorithm may move backward to ensure the monotone property holds. Finally, replace all digits to the right of the correction point with 9.
This greedy correction ensures the result is the largest valid number ≤ n. The algorithm runs in O(d) time where d is the number of digits.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy digit adjustment | O(d) where d is the number of digits in n | O(d) for digit storage (can be O(1) if modified in-place) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Build the answer digit by digit, adding the largest possible one that would make the number still less than or equal to N.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly used in coding interviews because it tests greedy reasoning and digit manipulation. Variants of this problem can appear in interviews at major tech companies.
A string or digit array is typically used so individual digits can be inspected and modified easily. This allows the algorithm to adjust digits and fill the remaining positions with 9 when necessary.
The optimal approach uses a greedy strategy. Convert the number into digits, find where the monotonic order breaks, decrement the offending digit, and set all digits to its right to 9 to maximize the valid number.
After fixing the digit that breaks the monotonic order, filling the remaining positions with 9 ensures the resulting number is as large as possible while still being less than or equal to the original number.