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 ton withmonotone increasing digits.

Examples

Example 1

1
2

Input: n = 10
Output: 9

Example 2

1
2

Input: n = 1234
Output: 1234

Example 3

1
2

Input: n = 332
Output: 299

Constraints

  • 0 <= n <= 10^9

Solution

Method 1 - Greedy Digit Manipulation

Intuition

We want the largest number ≤ n with digits in non-decreasing order. If a digit is greater than the next, we decrease it and set all following digits to 9.

Approach

Convert n to a list of digits. Scan from left to right, find the first place where digits[i] > digits[i+1], decrease digits[i] by 1, set all digits after i to 9, and repeat if needed. Convert back to integer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int mark = digits.length;
        for (int i = digits.length - 1; i > 0; i--) {
            if (digits[i] < digits[i-1]) {
                digits[i-1]--;
                mark = i;
            }
        }
        for (int i = mark; i < digits.length; i++) {
            digits[i] = '9';
        }
        return Integer.parseInt(new String(digits));
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def monotoneIncreasingDigits(n):
    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))

Complexity

  • ⏰ Time complexity: O(L) — L = number of digits in n.
  • 🧺 Space complexity: O(L) — For digit array.