LeetCode 738: Monotone Increasing Digits Solution

Master LeetCode problem 738 (Monotone Increasing Digits), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

738. Monotone Increasing Digits

Medium

Math Greedy

Problem Explanation

Explanation:

To find the largest number less than or equal to n with monotone increasing digits, we can start from the rightmost digit of n and move towards the left. At each step, we compare the current digit with the previous one. If the current digit is smaller than the previous one, we decrement the previous digit by one and set all subsequent digits to 9 to ensure monotone increasing digits.

Algorithm:

Convert the given integer n to an array of digits.
Iterate from the second last digit to the first digit of the array.
If the current digit is smaller than the previous digit, decrement the previous digit by one and set all subsequent digits to 9.
Convert the modified array back to an integer and return the result.

Time Complexity:

The time complexity of this algorithm is O(log n) as we are processing each digit of the input number.

Space Complexity:

The space complexity is O(log n) to store the digits of the input number.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 738 (Monotone Increasing Digits)?

This page provides optimized solutions for LeetCode problem 738 (Monotone Increasing Digits) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 738 (Monotone Increasing Digits)?

The time complexity for LeetCode 738 (Monotone Increasing Digits) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 738 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 738 in Java, C++, or Python.

Back to LeetCode Solutions