# 738. Monotone Increasing Digits

LeetCode Problem Link (opens new window)

Given a non-negative integer N, find the largest integer less than or equal to N with digits in non-decreasing order.

(A number is considered to have digits in non-decreasing order if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:

Input: N = 10
Output: 9

Example 2:

Input: N = 1234
Output: 1234

Example 3:

Input: N = 332
Output: 299

Explanation: N is in the range [0, 10^9].

# Approach

# Brute Force Approach

The problem is straightforward, and the first idea that comes to mind is a brute force approach. Let me demonstrate a brute force approach which leads to a timeout.

The code is as follows:

class Solution {
private:
    // Check if a number has digits in non-decreasing order
    bool checkNum(int num) {
        int max = 10;
        while (num) {
            int t = num % 10;
            if (max >= t) max = t;
            else return false;
            num = num / 10;
        }
        return true;
    }
public:
    int monotoneIncreasingDigits(int N) {
        for (int i = N; i > 0; i--) { // Traverse from large to small
            if (checkNum(i)) return i;
        }
        return 0;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Time Complexity: O(n × m), where m is the number of digits in n
Space Complexity: O(1)

# Greedy Algorithm

The problem asks for the largest monotone increasing integer less than or equal to N. Let's take a two-digit number as an example.

For instance: 98. Once a situation like strNum[i - 1] > strNum[i] occurs (not monotone increasing), the first thought is to make strNum[i - 1]--, then set strNum[i] to 9, thus making this integer 89, which is the largest monotone increasing integer less than 98.

If you understand this, the problem is easier to tackle.

Should we iterate from the beginning to the end or from the end to the beginning?

If we iterate from the beginning to the end and encounter strNum[i - 1] > strNum[i], decrementing strNum[i - 1] might result in yet another strNum[i - 2] > strNum[i - 1].

Let's look at an example, the number: 332. If we traverse from the beginning, it becomes 329, but then 2 is less than the first 3, and the actual result should be 299.

However, if we iterate from the end to the beginning, we can repeatedly use the result from the last comparison. The number 332 changes as follows: 332 -> 329 -> 299.

Once the traversal order is determined, the local optimum solution can lead to a global optimum. We should consider using a greedy approach.

C++ code is given below:

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // The flag is used to mark where to start setting to 9
        // Set to this default value to prevent the second for loop from executing without the flag being set
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i]) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};

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

Time Complexity: O(n), where n is the length of the number
Space Complexity: O(n), requires a string for easier operations

# Summary

The key to this problem is thinking through specific cases, such as 98, where you make strNum[i - 1]-- and set strNum[i] = 9 at strNum[i - 1] > strNum[i] to obtain 89, the largest monotone increasing number below 98. From there, it's straightforward to derive a greedy solution.

After deciding on a greedy approach, consider the traversal order. Only by iterating from the end to the beginning can we repeatedly use the results of the previous comparison.

Finally, some techniques are needed in code implementation, like using a flag to indicate where to start assigning 9.

# Other Language Versions

# Java

Version 1
class Solution {
    public int monotoneIncreasingDigits(int N) {
        String[] strings = (N + "").split("");
        int start = strings.length;
        for (int i = strings.length - 1; i > 0; i--) {
            if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                start = i;
            }
        }
        for (int i = start; i < strings.length; i++) {
            strings[i] = "9";
        }
        return Integer.parseInt(String.join("", strings));
    }
}

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

In Java Version 1, a String array was created, and the Integer.parseInt method was used multiple times. This resulted in high runtime and memory usage, taking 12ms. Below is a version that modifies in-place on a char array, taking 1ms.

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

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

# Python

Brute Force

class Solution:
    def checkNum(self, num):
        max_digit = 10
        while num:
            digit = num % 10
            if max_digit >= digit:
                max_digit = digit
            else:
                return False
            num //= 10
        return True

    def monotoneIncreasingDigits(self, N):
        for i in range(N, 0, -1):
            if self.checkNum(i):
                return i
        return 0

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

Greedy (Version One)

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # Convert integer to string
        strNum = str(n)
        # The flag is used to mark from where to start assigning 9
        # Initialized to the length of the string to prevent the second for loop from executing if flag hasn't been set
        flag = len(strNum)
        
        # Traverse the string from right to left
        for i in range(len(strNum) - 1, 0, -1):
            # If the current character is smaller than the previous one, modify the previous character
            if strNum[i - 1] > strNum[i]:
                flag = i  # Update flag to record where changes are needed
                # Decrement the previous character to ensure increasing order
                strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]
        
        # Set all characters from flag's position onwards to 9 to ensure the largest increasing number
        for i in range(flag, len(strNum)):
            strNum = strNum[:i] + '9' + strNum[i + 1:]
        
        # Convert the final string back to an integer and return
        return int(strNum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Greedy (Version Two)

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # Convert integer to string
        strNum = list(str(n))

        # Traverse the string from right to left
        for i in range(len(strNum) - 1, 0, -1):
            # If the current character is smaller than the previous one, modify the previous character
            if strNum[i - 1] > strNum[i]:
                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # Decrease the previous character
                # Set all characters past the modified position to 9 to maintain increasing order
                for j in range(i, len(strNum)):
                    strNum[j] = '9'

        # Convert the list back to a string, then to an integer, and return
        return int(''.join(strNum))

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

Greedy (Version Three)

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        # Convert integer to string
        strNum = list(str(n))

        # Traverse the string from right to left
        for i in range(len(strNum) - 1, 0, -1):
            # If the current character is smaller than the previous one, modify the previous character
            if strNum[i - 1] > strNum[i]:
                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # Decrease the previous character
                # Set all characters past the modified position to 9 to maintain increasing order
                strNum[i:] = '9' * (len(strNum) - i)

        # Convert the list back to a string, then to an integer, and return
        return int(''.join(strNum))

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

Greedy (Version Four) Simplified

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        strNum = str(n)        
        for i in range(len(strNum) - 1, 0, -1):
            # If the current character is smaller than the previous one, modify the previous character
            if strNum[i - 1] > strNum[i]:
                # Decrement the previous character to maintain increasing order
                strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)       
        return int(strNum)

1
2
3
4
5
6
7
8
9

# Go

func monotoneIncreasingDigits(n int) int {
    s := strconv.Itoa(n)
    // Traverse the string from left to right to find the first position that violates the monotone increasing order
    for i := len(s) - 2; i >= 0; i-- {
        if s[i] > s[i+1] {
            // Decrease the digit at this position
            s = s[:i] + string(s[i]-1) + s[i+1:]
            // Set all digits after this position to 9
            for j := i + 1; j < len(s); j++ {
                s = s[:j] + "9" + s[j+1:]
            }
        }
    }
    result, _ := strconv.Atoi(s)
    return result
}

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

# JavaScript

var monotoneIncreasingDigits = function(n) {
    n = n.toString()
    n = n.split('').map(item => {
        return +item
    })
    let flag = Infinity
    for(let i = n.length - 1; i > 0; i--) {
        if(n[i - 1] > n[i]) {
            flag = i
            n[i - 1] = n[i - 1] - 1
            n[i] = 9
        }
    }

    for(let i = flag; i < n.length; i++) {
        n[i] = 9
    }

    n = n.join('')
    return +n
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# TypeScript

function monotoneIncreasingDigits(n: number): number {
    let strArr: number[] = String(n).split('').map(i => parseInt(i));
    const length = strArr.length;
    let flag: number = length;
    for (let i = length - 2; i >= 0; i--) {
        if (strArr[i] > strArr[i + 1]) {
            strArr[i] -= 1;
            flag = i+1;
        }
    }
    for (let i = flag; i < length; i++) {
        strArr[i] = 9;
    }
    return parseInt(strArr.join(''));
};

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

# Scala

Directly converted into an integer array:

object Solution {
  import scala.collection.mutable
  def monotoneIncreasingDigits(n: Int): Int = {
    var digits = mutable.ArrayBuffer[Int]()
    // Extract each digit
    var temp = n // As the parameter n is immutable, it needs to be assigned to a mutable variable
    while (temp != 0) {
      digits.append(temp % 10)
      temp = temp / 10
    }
    // Greedily approach
    var flag = -1 
    for (i <- 0 until (digits.length - 1) if digits(i) < digits(i + 1)) {
      flag = i
      digits(i + 1) -= 1
    }
    for (i <- 0 to flag) digits(i) = 9

    // Combine the digits
    var res = 0
    for (i <- 0 until digits.length) {
      res += digits(i) * math.pow(10, i).toInt
    }
    res
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# Rust

impl Solution {
    pub fn monotone_increasing_digits(n: i32) -> i32 {
        let mut n_bytes = n.to_string().into_bytes();
        let mut flag = n_bytes.len();
        for i in (1..n_bytes.len()).rev() {
            if n_bytes[i - 1] > n_bytes[i] {
                flag = i;
                n_bytes[i - 1] -= 1;
            }
        }
        for v in n_bytes.iter_mut().skip(flag) {
            *v = 57;
        }
        n_bytes
            .into_iter()
            .fold(0, |acc, x| acc * 10 + x as i32 - 48)
    }
}

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

# C

int monotoneIncreasingDigits(int n) {
    char str[11];
    // Convert the number to a string
    sprintf(str, "%d", n);
    int len = strlen(str);
    int flag = strlen(str);
    for(int i = len - 1; i > 0; i--){
        if(str[i] < str[i - 1]){
            str[i - 1]--;
            flag = i;
        }
    }
    for(int i = flag; i < len; i++){
        str[i] = '9';
    }
    // Convert the string back to a number
    return atoi(str);
}

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

# C#

public class Solution
{
    public int MonotoneIncreasingDigits(int n)
    {
        char[] s = n.ToString().ToCharArray();
        int flag = s.Length;
        for (int i = s.Length - 1; i > 0; i--)
        {
            if (s[i - 1] > s[i])
            {
                flag = i;
                s[i - 1]--;
            }
        }
        for (int i = flag; i < s.Length; i++)
        {
            s[i] = '9';
        }
        return int.Parse(new string(s));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

← 17. Merge Intervals 19. Binary Tree Cameras →