Monotone Increasing Digits solution and explanation
Google
9 more videos on this problem
Monotone Increasing Digits LeetCode #738Geek gang · 18:08 · 3K views
Monotone Increasing Digits Tamil Tutorial (LeetCode 738 Medium)Akhil Chakravarthy - Tamil Coding Tutorials · 6:34 · 1K views
LeetCode 738 | Monotone Increasing Digits | Step by Step Explanation in Hindi | Java SolutionCode Kage · 10:10 · 222 views
Leetcode 738. Monotone Increasing Digits (greedy)LetsCode · 12:24 · 207 views
贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字 | 738. Monotone Increasing Digits代码随想录 · 14:32 · 153 views
Monotone Increasing Digits, Medium, C++, LeetCodeH William Polenz · 1:09:32 · 144 views
No Sound Leetcode 738: Monotone Increasing DigitsExtremeProgrammer · 1:39 · 33 views
Monotone Increasing Digits - Leetcode 738 - PythonThe Leetcode Addict · 9:45 · 21 views
LeetCode 738: Monotone Increasing DigitsAlitaCode · 28:08 · 9 views
LeetCode Problem #738 Monotone Increasing Digits神戸万事屋 · 0:43
The problem
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 <= 109
Approach overview
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.
Approach 1: Greedy Approach
This approach involves greedy deduction; when a decrease in a sequence is detected (previous digit is greater than the next), we can decrease the previous digit by 1 and set all following digits to 9, ensuring the property of monotonic sequence.
def monotoneIncreasingDigits(N: int) -> int:
str_n = list(str(N))
marker = len(str_n)
for i in range(len(str_n) - 1, 0, -1):
if str_n[i] < str_n[i - 1]:
marker = i
str_n[i - 1] = str(int(str_n[i - 1]) - 1)
for i in range(marker, len(str_n)):
str_n[i] = '9'
return int(''.join(str_n))class Solution {
public int monotoneIncreasingDigits(int n) {
char[] str = String.valueOf(n).toCharArray();
int marker = str.length;
for (int i = str.length - 1; i > 0; i--) {
if (str[i] < str[i - 1]) {
marker = i;
str[i - 1]--;
}
}
for (int i = marker; i < str.length; i++) {
str[i] = '9';
}
return Integer.parseInt(new String(str));
}
}#include <string>
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string str = to_string(n);
int marker = str.size();
for (int i = str.size() - 1; i > 0; --i) {
if (str[i] < str[i - 1]) {
marker = i;
str[i - 1]--;
}
}
for (int i = marker; i < str.size(); ++i) {
str[i] = '9';
}
return stoi(str);
}
};function monotoneIncreasingDigits(N) {
let strN = N.toString().split('');
let marker = strN.length;
for (let i = strN.length - 1; i > 0; --i) {
if (strN[i] < strN[i - 1]) {
marker = i;
strN[i - 1] = (strN[i - 1] - 1).toString();
}
}
for (let i = marker; i < strN.length; ++i) {
strN[i] = '9';
}
return parseInt(strN.join(''));
}#include <stdio.h>
int monotoneIncreasingDigits(int n) {
char str[11];
sprintf(str, "%d", n);
int len = strlen(str);
int marker = len;
for (int i = len - 1; i > 0; i--) {
if (str[i] < str[i - 1]) {
marker = i;
str[i - 1]--;
}
}
for (int i = marker; i < len; i++) {
str[i] = '9';
}
return atoi(str);
}public class Solution {
public int MonotoneIncreasingDigits(int n) {
char[] str = n.ToString().ToCharArray();
int marker = str.Length;
for (int i = str.Length - 1; i > 0; i--) {
if (str[i] < str[i - 1]) {
marker = i;
str[i - 1]--;
}
}
for (int i = marker; i < str.Length; i++) {
str[i] = '9';
}
return int.Parse(new string(str));
}
}The Python approach is typical of interpreting the number into a character list, facilitating alterations whenever a monotonic descent in the array is detected. This adjustive progression shifts and resets the latter parts to 9.
Time Complexity: O(d) due to single traversal through the digit array. Space Complexity: O(d) for the space used by the character list.
Approach 2: Default Approach
func monotoneIncreasingDigits(n int) int {
s := []byte(strconv.Itoa(n))
i := 1
for ; i < len(s) && s[i-1] <= s[i]; i++ {
}
if i < len(s) {
for ; i > 0 && s[i-1] > s[i]; i-- {
s[i-1]--
}
i++
for ; i < len(s); i++ {
s[i] = '9'
}
}
ans, _ := strconv.Atoi(string(s))
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(d) due to single traversal through the digit array. Space Complexity: O(d) for the space used by the character list. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Decrement and Check | O(n * d) | O(d) | Useful for understanding the definition of monotone digits or when n is very small |
| Greedy Digit Adjustment | O(d) | O(d) | Optimal solution for interviews and large inputs; modifies digits once and maximizes suffix with 9s |
Frequently asked questions
Is Monotone Increasing Digits easy or hard?
Monotone Increasing Digits is classified as a medium difficulty problem. The challenge comes from recognizing the greedy correction strategy and handling cascading digit decreases when the monotone condition breaks.
Monotone Increasing Digits Python/Java solution
Implementations typically convert the number to a string or digit list, perform the greedy adjustment, then rebuild the final number. The same logic works across Python, Java, C++, C#, and JavaScript since it only relies on digit traversal and basic arithmetic operations.
How to solve Monotone Increasing Digits in O(n)?
Treat the number as a digit array and scan for the first violation where digit[i] < digit[i-1]. Decrement the previous digit and propagate the correction backward if needed. After fixing the prefix, set all remaining digits to 9 to maximize the number while maintaining the monotone condition.
What is the best approach for Monotone Increasing Digits?
The greedy digit-adjustment approach is the optimal method. Convert the number into digits, detect where the monotone order breaks, decrement the previous digit, and fill the remaining suffix with 9s. This guarantees the largest number less than or equal to n with non‑decreasing digits and runs in O(d) time where d is the number of digits.
Is Monotone Increasing Digits asked at Google/Amazon/Meta?
Monotone Increasing Digits represents a common greedy digit manipulation pattern often discussed in coding interviews. Variants of this style of problem appear in interviews at large tech companies such as Google, Amazon, and Meta, especially when testing greedy reasoning and number manipulation skills.
What data structure is used in Monotone Increasing Digits?
Most solutions convert the integer into a string or array of digits so each position can be modified individually. The algorithm then performs simple index-based iteration and updates, making the digit array the primary structure used during computation.
What is the time complexity of Monotone Increasing Digits?
The optimal greedy solution runs in O(d) time and O(d) space, where d is the number of digits in the input number. Each digit is inspected and possibly adjusted once, making the algorithm extremely efficient compared to brute force approaches.