Leetcode 738. Monotone Increasing Digits

Problem explanation

The problem requires finding the largest number with monotone increasing digits that is less than or equal to a given non-negative integer N. A number has monotone increasing digits if each digit is less than or equal to the digit right after it.

For example, if the given number is 332, it contains a pair of adjacent digits (3, 2) that does not satisfy the condition of monotone increasing digits (3 > 2). In such a case, we would need to convert this number into the largest number that satisfies the condition of monotone increasing digits and is less than 332, which is 299.

On the other hand, if the given number is 1234, it already satisfies the condition of monotone increasing digits (as 1 <= 2, 2 <= 3, and 3 <= 4), and thus, the output of the function would be 1234 (the same input number).

Solution explanation

The algorithm follows this steps:

1. Convert the number to a string for easy manipulation of digits.
2. Iterate over the digits from right to left.
3. If a digit is less than the one to its right, subtract one from the current digit and change all the digits to its right to 9. This ensures that the new number is less than the original number but also the largest number with monotone increasing digits.
4. Convert the string back to an integer before returning the result.

Python solution

1
2python
3class Solution:
4    def monotoneIncreasingDigits(self, N: int) -> int:
5        # Convert the number to a string for easy manipulation of digits
6        number_str = list(str(N))
7        i = len(number_str) - 1
8        
9        while i > 0:
10            # If current digit is smaller than previous digit
11            if number_str[i] < number_str[i-1]:
12                # Subtract 1 from previous digit
13                number_str[i-1] = str(int(number_str[i-1]) - 1)
14                # Set current digit and all following digits to '9'
15                for j in range(i, len(number_str)):
16                    number_str[j] = '9'
17            i -= 1
18
19        return int(''.join(number_str))

Java solution

1
2java
3class Solution {
4    public int monotoneIncreasingDigits(int N) {
5        char[] digits = Integer.toString(N).toCharArray();
6        int i, j;
7        for (i = 1; i < digits.length && digits[i-1] <= digits[i]; i++);
8        if(i < digits.length) {
9            for (j = i; j > 0 && digits[j-1] > digits[j]; j--)
10                digits[j-1]--;
11            for (j++; j < digits.length; j++)
12                digits[j] = '9';
13        }
14        return Integer.parseInt(new String(digits));
15    }
16}

JavaScript solution

1
2javascript
3var monotoneIncreasingDigits = function(N) {
4    const chars = N.toString().split('');
5    let i = 1;
6    while (i < chars.length && chars[i-1] <= chars[i]) i++;
7    while (0 < i && i < chars.length && chars[i-1] > chars[i]) chars[--i]--;
8    for (i++; i < chars.length; i++) chars[i] = '9';
9
10    return Number(chars.join(''));
11};

C++ solution

1
2cpp
3class Solution {
4public:
5    int monotoneIncreasingDigits(int N) {
6        string num = to_string(N);
7        int mark = num.size();
8        for(int i = num.size()-1; i > 0; i--){
9            if(num[i] < num[i-1]){
10                mark = i;
11                num[i-1]--;
12            }
13        }
14        for(int i = mark; i < num.size(); i++)
15            num[i] = '9';
16        return stoi(num);
17    }
18};

C# solution

1
2csharp
3public class Solution {
4    public int MonotoneIncreasingDigits(int N) {
5        string strN = N.ToString();
6        char[] arr = strN.ToCharArray();
7
8        int i = 1;
9        while (i < arr.Length && arr[i - 1] <= arr[i]) i++;
10
11        if (i < arr.Length) {
12            while (i > 0 && arr[i - 1] > arr[i]) arr[--i]--;
13            for (i++; i < arr.Length; i++) arr[i] = '9';
14        }
15        
16        return Int32.Parse(new string(arr));
17    }
18}

Swift solution

1
2swift
3class Solution {
4    func monotoneIncreasingDigits(_ N: Int) -> Int {
5        var chars = Array(String(N))
6        var i = 1
7        while i < chars.count && chars[i-1] <= chars[i] {
8            i += 1
9        }
10        if i < chars.count {
11            while i > 0 && chars[i-1] > chars[i] {
12                chars[i-1] = Character(String(Int(String(chars[i-1]))! - 1))
13                i -= 1
14            }
15            for j in i..<chars.count {
16                chars[j] = "9"
17            }
18        }
19        return Int(String(chars))!
20    }
21}

This Swift solution follows the same steps as the previous ones. We start by converting the given integer N to a String and then to an Array of Characters to be able to manipulate its individual digits. Then, we iterate through the characters, compare each one to the previous one, and adjust the digits accordingly to ensure we form the largest possible number with monotonically increasing digits.

Kotlin solution

1
2kotlin
3class Solution {
4    fun monotoneIncreasingDigits(N: Int): Int {
5        val chars = N.toString().toCharArray()
6        var i = 1
7        while (i < chars.size && chars[i - 1] <= chars[i]) i++
8        while (i > 0 && i < chars.size && chars[i - 1] > chars[i]) {
9            chars[--i]--
10        }
11        for (index in i + 1 until chars.size) {
12            chars[index] = '9'
13        }
14        return String(chars).toInt()
15    }
16}

In this Kotlin solution, we convert the given integer N to a String and then to a CharArray so that we can manipulate its individual digits. We then use two while loops to adjust the digits to form the largest number with monotonically increasing digits.

We hope this comprehensive list of solutions helps you understand how to solve the given problem using different programming languages efficiently. Remember that understanding the algorithm is more important than the programming language used to implement it. If you understand the solution well, you can implement it in any programming language of your choice.