# LeetCode 738: Monotone Increasing Digits

## Problem Restatement

We are given a non-negative integer `n`.

We need to return the largest integer less than or equal to `n` whose digits are monotone increasing.

A number has monotone increasing digits when every adjacent digit pair satisfies:

```text
left_digit <= right_digit
```

For example:

```text
1234 is valid
1119 is valid
332 is not valid
```

The official constraint is:

```text
0 <= n <= 10^9
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A non-negative integer `n` |
| Output | The largest integer `<= n` with monotone increasing digits |
| Valid digit order | Each digit must be less than or equal to the next digit |

Example function shape:

```python
def monotoneIncreasingDigits(n: int) -> int:
    ...
```

## Examples

### Example 1

```python
n = 10
```

`10` is not monotone increasing because:

```text
1 > 0
```

The largest valid number less than or equal to `10` is:

```python
9
```

### Example 2

```python
n = 1234
```

Every adjacent pair is valid:

```text
1 <= 2 <= 3 <= 4
```

So the answer is:

```python
1234
```

### Example 3

```python
n = 332
```

`332` is not valid because:

```text
3 <= 3, but 3 > 2
```

To make the number smaller but as large as possible, reduce the first problematic `3` group and fill the rest with `9`.

The answer is:

```python
299
```

## First Thought: Check Numbers Downward

One direct method is to start from `n` and check each number going downward.

For each number, test whether its digits are monotone increasing.

This works, but it can be far too slow.

If `n` is close to `10^9`, we may need to check many numbers.

We need to modify the digits of `n` directly.

## Key Insight

If the digits are already monotone increasing, `n` itself is the answer.

If we find a violation:

```text
digits[i - 1] > digits[i]
```

then the prefix ending at `i - 1` is too large.

To get the largest valid number less than `n`, we should:

1. Decrease some digit on the left by `1`.
2. Set every digit after it to `9`.

Why `9`?

Once the prefix is made smaller, the suffix should be as large as possible. The largest possible suffix is all `9`s.

But there is one subtle point.

For:

```python
n = 1332
```

The violation is `3 > 2`.

If we only reduce the second `3`, we get:

```python
1322
```

This is still invalid because:

```text
3 > 2
```

So we scan from right to left. Whenever a digit is smaller than the digit before it, decrement the previous digit and mark the suffix to become `9`.

## Algorithm

Convert `n` to a list of digit characters.

Let:

```python
mark = len(digits)
```

`mark` is the first position that should become `9`.

Scan from right to left.

For each index `i` from `len(digits) - 1` down to `1`:

1. If `digits[i] < digits[i - 1]`:
   - Decrement `digits[i - 1]`.
   - Set `mark = i`.

After the scan, set every digit from `mark` to the end to `'9'`.

Convert the digit list back to an integer.

## Correctness

Whenever `digits[i] < digits[i - 1]`, the number violates the monotone increasing rule at positions `i - 1` and `i`.

Any valid number less than or equal to the original number must reduce some digit at or before `i - 1`; otherwise, the same invalid prefix would remain. The greedy step reduces `digits[i - 1]` by exactly `1`, which makes the prefix as large as possible while moving below the invalid value.

After the prefix has been reduced, the largest possible suffix is all `9`s. Setting the suffix to `9` therefore maximizes the final number among numbers with that reduced prefix.

Scanning from right to left handles cascades correctly. If decrementing one digit creates a new violation with the digit before it, the later leftward scan will detect and fix it. This is why cases like `1332` become `299`, not `1329`.

After the scan finishes, no adjacent pair before `mark` violates the monotone rule. All digits from `mark` onward are `9`, so they cannot create a violation with later digits. Therefore the result is monotone increasing.

The algorithm only reduces digits when required by a violation, and each reduction is minimal. The suffix is then maximized with `9`s. Therefore the returned number is the largest monotone increasing number less than or equal to `n`.

## Complexity

Let `d` be the number of digits in `n`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(d)` | We scan the digits once and fill a suffix once |
| Space | `O(d)` | The digit list stores the decimal representation |

Since `n <= 10^9`, `d` is at most `10`.

## Implementation

```python
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        digits = list(str(n))
        mark = len(digits)

        for i in range(len(digits) - 1, 0, -1):
            if digits[i] < digits[i - 1]:
                digits[i - 1] = str(int(digits[i - 1]) - 1)
                mark = i

        for i in range(mark, len(digits)):
            digits[i] = "9"

        return int("".join(digits))
```

## Code Explanation

We convert the number into digits:

```python
digits = list(str(n))
```

This lets us change individual digits.

The variable `mark` stores where the suffix of `9`s should begin:

```python
mark = len(digits)
```

If the number is already valid, `mark` stays at the end, and no digit is changed to `9`.

We scan from right to left:

```python
for i in range(len(digits) - 1, 0, -1):
```

When a violation is found:

```python
if digits[i] < digits[i - 1]:
```

we decrement the previous digit:

```python
digits[i - 1] = str(int(digits[i - 1]) - 1)
```

and remember that position `i` and everything after it should become `9`:

```python
mark = i
```

After all fixes, fill the suffix:

```python
for i in range(mark, len(digits)):
    digits[i] = "9"
```

Finally, convert back to an integer:

```python
return int("".join(digits))
```

This automatically handles leading zero cases. For example, `10` becomes `"09"`, and `int("09")` returns `9`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.monotoneIncreasingDigits(10) == 9
    assert s.monotoneIncreasingDigits(1234) == 1234
    assert s.monotoneIncreasingDigits(332) == 299
    assert s.monotoneIncreasingDigits(0) == 0
    assert s.monotoneIncreasingDigits(9) == 9
    assert s.monotoneIncreasingDigits(120) == 119
    assert s.monotoneIncreasingDigits(1332) == 1299
    assert s.monotoneIncreasingDigits(1000) == 999
    assert s.monotoneIncreasingDigits(987654321) == 899999999

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `10` | Leading zero after adjustment becomes `9` |
| `1234` | Already monotone increasing |
| `332` | Standard decreasing suffix case |
| `0` | Minimum value |
| `9` | Single digit |
| `120` | Violation near the end |
| `1332` | Repeated digit before violation |
| `1000` | Large suffix becomes all `9`s |
| `987654321` | Many cascading fixes |