Monotone Increasing Digits
MedPrompt
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: 9Example 2:
Input: n = 1234
Output: 1234Example 3:
Input: n = 332
Output: 299
Constraints:
0 <= n <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every integer, starting from n and going downwards, until we find one that has monotone increasing digits. For each integer, we verify the property by comparing its adjacent digits.
Algorithm
- Start a loop with a variable
iinitialized ton. - In each iteration, check if the number
ihas monotone increasing digits. - To perform the check, create a helper function
isMonotone(num):- Convert
numto its string representation,s. - Iterate through the string
sfrom the first character to the second-to-last character. - If at any point
s.charAt(j) > s.charAt(j+1), the number is not monotone, so returnfalse. - If the loop completes without finding such a violation, return
true.
- Convert
- If
isMonotone(i)returnstrue, theniis the largest monotone increasing number less than or equal ton. Returni. - If not, decrement
iand continue the loop. - The loop will eventually terminate because 0 is a monotone increasing number.
Walkthrough
The most straightforward way to solve this problem is to use a brute-force search. We start with the given number n and check if it satisfies the monotone increasing digit property. If it does, we have found our answer since we are looking for the largest number less than or equal to n. If it doesn't, we decrement the number by one and repeat the process. We continue this until we find a valid number. Since 0 is a valid monotone increasing number, this process is guaranteed to terminate.
A helper function can be used to check if a number is monotone increasing. This function would convert the number to a string or an array of digits and then iterate through them, ensuring that each digit is less than or equal to the next one.
Here is a code snippet for this approach:
class Solution { public int monotoneIncreasingDigits(int n) { for (int i = n; i >= 0; i--) { if (isMonotone(i)) { return i; } } return 0; // Should not be reached for n >= 0 } private boolean isMonotone(int num) { String s = String.valueOf(num); for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) > s.charAt(i + 1)) { return false; } } return true; }}Complexity
Time
O(N * D), where N is the input number and D is the number of digits in N (D = log₁₀N). In the worst-case scenario (e.g., n = 100000000), we might have to check many numbers. This complexity is too high for the given constraint `n <= 10^9`.
Space
O(D) or O(log n), where D is the number of digits in n. This space is used to store the string representation of the number being checked.
Trade-offs
Pros
Simple to understand and implement.
Correct for all valid inputs, given enough time.
Cons
Extremely inefficient for large values of
n.Will likely cause a 'Time Limit Exceeded' (TLE) error on most online judges for the given constraints.
Solutions
Solution
class Solution {public int monotoneIncreasingDigits(int n) { char[] s = String.valueOf(n).toCharArray(); int i = 1; for (; i < s.length && s[i - 1] <= s[i]; ++i) ; if (i < s.length) { for (; i > 0 && s[i - 1] > s[i]; --i) { --s[i - 1]; } ++i; for (; i < s.length; ++i) { s[i] = '9'; } } return Integer.parseInt(String.valueOf(s)); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.