# Monotone Increasing Digits
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/monotone-increasing-digits)
Canonical: https://scaleengineer.com/dsa/problems/monotone-increasing-digits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [SAP](https://scaleengineer.com/companies/sap)
---
## Problem
An integer has **monotone increasing digits** if and only if each pair of adjacent digits `x` and `y` satisfy `x <= y`.

Given an integer `n`, return _the largest number that is less than or equal to_ `n` _with **monotone increasing digits**_.

**Example 1:**

**Input:** n = 10
**Output:** 9

**Example 2:**

**Input:** n = 1234
**Output:** 1234

**Example 3:**

**Input:** n = 332
**Output:** 299

**Constraints:**

* `0 <= n <= 109`

# Approaches
## Brute Force Iteration
This approach involves checking every integer, starting from `n` and going downwards, until we find one that has monotone increasing digits. For each integer, we verify the property by comparing its adjacent digits.
**Time:** O(N * D), where N is the input number and D is the number of digits in N (D = log₁₀N). In the worst-case scenario (e.g., n = 100000000), we might have to check many numbers. This complexity is too high for the given constraint `n <= 10^9`. · **Space:** O(D) or O(log n), where D is the number of digits in n. This space is used to store the string representation of the number being checked.
**Pros:** Simple to understand and implement.; Correct for all valid inputs, given enough time.
**Cons:** Extremely inefficient for large values of `n`.; Will likely cause a 'Time Limit Exceeded' (TLE) error on most online judges for the given constraints.
### Explanation
The most straightforward way to solve this problem is to use a brute-force search. We start with the given number `n` and check if it satisfies the monotone increasing digit property. If it does, we have found our answer since we are looking for the largest number less than or equal to `n`. If it doesn't, we decrement the number by one and repeat the process. We continue this until we find a valid number. Since 0 is a valid monotone increasing number, this process is guaranteed to terminate.

A helper function can be used to check if a number is monotone increasing. This function would convert the number to a string or an array of digits and then iterate through them, ensuring that each digit is less than or equal to the next one.

Here is a code snippet for this approach:
```java
class Solution {
    public int monotoneIncreasingDigits(int n) {
        for (int i = n; i >= 0; i--) {
            if (isMonotone(i)) {
                return i;
            }
        }
        return 0; // Should not be reached for n >= 0
    }

    private boolean isMonotone(int num) {
        String s = String.valueOf(num);
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) > s.charAt(i + 1)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Start a loop with a variable `i` initialized to `n`.
- In each iteration, check if the number `i` has monotone increasing digits.
- To perform the check, create a helper function `isMonotone(num)`:
  - Convert `num` to its string representation, `s`.
  - Iterate through the string `s` from the first character to the second-to-last character.
  - If at any point `s.charAt(j) > s.charAt(j+1)`, the number is not monotone, so return `false`.
  - If the loop completes without finding such a violation, return `true`.
- If `isMonotone(i)` returns `true`, then `i` is the largest monotone increasing number less than or equal to `n`. Return `i`.
- If not, decrement `i` and continue the loop.
- The loop will eventually terminate because 0 is a monotone increasing number.

## Greedy Approach with Right-to-Left Scan
A much more efficient method is a greedy approach. We can construct the result by modifying the digits of `n`. The idea is to find the first violation of the monotone property from left to right, say at index `i` where `digit[i-1] > digit[i]`. To fix this, we must decrement `digit[i-1]` and, to maximize the number, set all subsequent digits to '9'. A clever way to implement this is to scan the digits from right to left.
**Time:** O(D), where D is the number of digits in n (D = log₁₀n). The algorithm involves a few passes over the digits of the number, making it very fast. · **Space:** O(D) or O(log n), where D is the number of digits in n. This space is required to store the character array representation of the number.
**Pros:** Highly efficient and optimal.; Solves the problem in linear time with respect to the number of digits.
**Cons:** Slightly more complex to reason about compared to the brute-force approach.; Requires conversion to and from a string/character array representation.
### Explanation
This greedy algorithm works by identifying the point of non-monotonicity and correcting it to form the largest possible valid number. We want to keep the most significant digits as large as possible, which means we want to preserve the prefix of `n` as much as we can.

We can process the digits of `n` as a character array. A right-to-left scan is particularly effective. We iterate from the end of the number towards the beginning. If we find a pair of adjacent digits `s[i-1]` and `s[i]` such that `s[i-1] > s[i]`, we've found a "cliff". To make the number monotone, we must decrease `s[i-1]`. After decrementing `s[i-1]`, all digits to its right should be set to '9' to make the resulting number as large as possible. The right-to-left scan naturally handles cases where decrementing a digit causes a new violation with the digit to its left (e.g., in `332`, changing the second `3` to `2` makes the number `322`, which is still not monotone).

For example, with `n = 332`:
1. `s = ['3', '3', '2']`.
2. Scan from right. At `i=2`, we compare `s[1]` and `s[2]`. `3 > 2` is a violation.
3. We decrement `s[1]` to `'2'`. The array becomes `['3', '2', '2']`. We record that digits from index `2` onwards should be '9'.
4. Continue scan. At `i=1`, we compare `s[0]` and `s[1]`. Now `3 > 2` is a violation.
5. We decrement `s[0]` to `'2'`. The array becomes `['2', '2', '2']`. We update our record: digits from index `1` onwards should be '9'.
6. After the scan, we apply the change: set digits from index 1 to the end to '9'. The array becomes `['2', '9', '9']`.
7. The result is 299.

Here is the code for this approach:
```java
class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int len = s.length;
        int marker = len;
        // Scan from right to left to find the first cliff
        for (int i = len - 1; i > 0; i--) {
            if (s[i] < s[i - 1]) {
                // Decrement the digit at the cliff
                s[i - 1]--;
                // Mark the starting position for filling with 9s
                marker = i;
            }
        }
        // Fill all digits from the marker to the end with '9'
        for (int i = marker; i < len; i++) {
            s[i] = '9';
        }
        return Integer.parseInt(new String(s));
    }
}
```
### Algorithm
- Convert the input integer `n` to a character array `s`.
- Initialize an integer `marker` to the length of `s`. This `marker` will point to the first digit (from the left) that needs to be changed to '9'.
- Iterate through the character array `s` from right to left, starting from the second to last digit (`i = s.length - 2` down to `0`).
- In each iteration, compare `s[i]` with `s[i+1]`.
- If `s[i] > s[i+1]`, a violation is found. This means the prefix ending at `s[i]` is too large.
  - To correct this, decrement the character `s[i]` by one.
  - Update `marker` to `i + 1`, as all digits from this position onwards must be '9' to maximize the resulting number.
- After the loop finishes, iterate from `marker` to the end of the array (`j = marker` to `s.length - 1`).
- Set `s[j]` to '9'.
- Finally, convert the modified character array `s` back to an integer and return it.

# Solutions
### Java

```java
class Solution {
public
  int monotoneIncreasingDigits(int n) {
    char[] s = String.valueOf(n).toCharArray();
    int i = 1;
    for (; i < s.length && s[i - 1] <= s[i]; ++i)
      ;
    if (i < s.length) {
      for (; i > 0 && s[i - 1] > s[i]; --i) {
        --s[i - 1];
      }
      ++i;
      for (; i < s.length; ++i) {
        s[i] = '9';
      }
    }
    return Integer.parseInt(String.valueOf(s));
  }
}

```

### CPP

```cpp
class Solution {
public:
  int monotoneIncreasingDigits(int n) {
    string s = to_string(n);
    int i = 1;
    for (; i < s.size() && s[i - 1] <= s[i]; ++i)
      ;
    if (i < s.size()) {
      for (; i > 0 && s[i - 1] > s[i]; --i) {
        --s[i - 1];
      }
      ++i;
      for (; i < s.size(); ++i) {
        s[i] = '9';
      }
    }
    return stoi(s);
  }
};

```

### Python

```python
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int: s = list(str(n)) i = 1 while i < len(s) and s[i - 1] <= s[i]: i += 1 if i < len(s): while i and s[i - 1] > s[i]: s[i - 1] = str(int(s[i - 1]) - 1) i -= 1 i += 1 while i < len(s): s[i] = '9' i += 1 return int('' . join(s))

```