Monotone Increasing Digits — Solution in Python, Java & C++
Monotone Increasing Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Monotone Increasing Digits is a medium coding problem on math and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An integer has monotone increasing digits if each digit is at least as large as the one before it.
Given an integer n, return the largest number less than or equal to n with monotone increasing digits.
Example 1
Input: n = 10
Output: 9
Example 2
Input: n = 1234
Output: 1234
Explanation: It already qualifies.
Example 3
Input: n = 332
Output: 299
Constraints
0 <= n <= 100000000
Hints for Monotone Increasing Digits
Hint 1
Walk the digits from the right. Wherever a digit is smaller than the one before it, that earlier digit must come down by one.
Hint 2
Everything after the last such break can then be raised to 9.
Hint 3
Do the scan right to left in one pass so cascading breaks (like 332 → 329 → 299) resolve correctly.
How to solve Monotone Increasing Digits
Scan right to left; wherever a digit is smaller than its predecessor, decrement the predecessor and mark the position; then set everything after the last mark to 9.
Approach
- For
ifrom the end down to 1, ifd[i-1] > d[i]:d[i-1] -= 1,mark = i. - Set
d[j] = 9forj >= mark. - Parse the digits.
Why it works
The largest monotone number ≤ n shares the longest possible prefix with n; at the first break the prefix digit must drop by one, and the suffix is then free to be all 9s. Scanning right to left resolves cascades (332 → 299).
Complexity
- Time —
O(digits) - Space —
O(digits)
Pitfalls
- A left-to-right scan misses cascades where the decrement creates a new break.
Reference solution
Python
def monotoneIncreasingDigits(n: int) -> int:
digits = [int(c) for c in str(n)]
mark = len(digits)
for i in range(len(digits) - 1, 0, -1):
if digits[i - 1] > digits[i]:
digits[i - 1] -= 1
mark = i
for i in range(mark, len(digits)):
digits[i] = 9
return int("".join(str(d) for d in digits))Java
public static int monotoneIncreasingDigits(int n) {
char[] digits = String.valueOf(n).toCharArray();
int mark = digits.length;
for (int i = digits.length - 1; i > 0; i--) {
if (digits[i - 1] > digits[i]) {
digits[i - 1]--;
mark = i;
}
}
for (int i = mark; i < digits.length; i++) digits[i] = '9';
return Integer.parseInt(new String(digits));
}C++
int monotoneIncreasingDigits(int n) {
string digits = to_string(n);
int mark = (int) digits.size();
for (int i = (int) digits.size() - 1; i > 0; i--) {
if (digits[i - 1] > digits[i]) {
digits[i - 1]--;
mark = i;
}
}
for (int i = mark; i < (int) digits.size(); i++) digits[i] = '9';
return stoi(digits);
}JavaScript
var monotoneIncreasingDigits = function(n) {
const digits = String(n).split("").map(Number);
let mark = digits.length;
for (let i = digits.length - 1; i > 0; i--) {
if (digits[i - 1] > digits[i]) {
digits[i - 1]--;
mark = i;
}
}
for (let i = mark; i < digits.length; i++) digits[i] = 9;
return parseInt(digits.join(""), 10);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Greedy Algorithms