Monotone Increasing Digits

The key idea

Scan the digits from right to left. At the first place where a digit is bigger than the one after it, drop that digit by 1 and force every digit after that position to 9. Track the leftmost spot you broke so the trailing nines start from the right place.

Problem

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfies x <= y. Given an integer n, return the largest number that is less than or equal to n and has monotone increasing digits.

Constraints

0 <= n <= 10^9

Examples

Input: n = 10 Output: 9

Input: n = 1234 Output: 1234

Input: n = 332 Output: 299

Complexity

Time: O(d) Space: O(d)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →