Find the Largest Monotone Increasing Number
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Find the Largest Monotone Increasing Number
## Problem
Given a non-negative integer `n`, return the largest integer less than or equal to `n` whose decimal digits are monotone increasing. Digits are monotone increasing when each digit is less than or equal to the digit immediately after it.
Implement:
```python
def largest_monotone_increasing(n: int) -> int:
...
```
## Constraints
- `0 <= n <= 10^18`
- The answer must not contain leading zeros, except that the number `0` is valid.
- Repeated adjacent digits are allowed.
## Examples
```text
n = 10 -> 9
n = 1234 -> 1234
n = 332 -> 299
n = 120 -> 119
n = 1000 -> 999
```
## Performance Goal
Use time linear in the number of decimal digits. Your explanation should cover why fixing one decreasing boundary may require revisiting earlier digits and why the suffix can be chosen greedily after that point.
Quick Answer: Find the largest number no greater than n whose decimal digits are monotone increasing. Develop a linear-time greedy correction that revisits earlier decreasing boundaries and fills the remaining suffix optimally without introducing leading zeros.
Given a nonnegative integer n, return the largest integer at most n whose decimal digits are nondecreasing from left to right. Repeated digits are allowed and the answer has no leading zeros except for zero.
Constraints
- n is between 0 and 10^18 inclusive.
- Each digit must be no greater than the next digit.
- Repeated adjacent digits are allowed.
- Return an integer without leading zeros.
- Use time linear in the number of digits.
Examples
Input: (0,)
Expected Output: 0
Explanation: Zero is a valid monotone number.
Input: (9,)
Expected Output: 9
Explanation: Every one-digit number is monotone.
Hints
- Scan a mutable digit list from right to left.
- When a decreasing boundary appears, decrement its left digit and remember where the suffix begins.
- Set every digit after the earliest repair point to 9.