Monotone Increasing Digits
Medium · Greedy · Math · Greedy
Problem
A non-negative integer has monotone increasing digits when each digit is less than or equal to the digit to its right. For example 1224 and 7 qualify, but 1321 does not (3 is followed by 2).
Given an integer n, return the largest integer that is at most n and has monotone increasing digits.
Examples
Input: n = 230 Output: 229
3 > 0 is a drop, so the 3 becomes 2 and the digits after it become 9: 229.
Input: n = 1357 Output: 1357
The digits never decrease, so n is the answer.
Input: n = 5553 Output: 4999
Lowering the last 5 makes it smaller than the 5 before it, and so on to the front: 4999.
Constraints
- 0 <= n <= 10^9
Approaches
- Build every monotone number up to n — time O(C(d + 9, 9)), space O(d)
Follow-up
Why is the result the largest? Any number at most n with monotone digits must agree with n up to the first position it is smaller, and there the right-to-left scan lowers exactly the digit it must. The same lower-one-digit-then-fill trick finds the largest number at most n for other digit rules too, such as non-increasing digits.
Related problems
Start free on Cariara · Coding problems · System design studio
