We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Monotone Increasing Digits

Difficulty: Medium

Problem Description

Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits. An integer has monotone increasing digits if each pair of adjacent digits x and y satisfy x <= y.

Key Insights

  • The digits of the number must be non-decreasing from left to right.
  • If a digit violates the monotone increasing property, we can decrease that digit and set all subsequent digits to 9 to maximize the number while still being less than or equal to n.
  • The solution involves identifying the first violation from left to right and adjusting the number accordingly.

Space and Time Complexity

Time Complexity: O(d), where d is the number of digits in the number n. Space Complexity: O(1), as we are using a constant amount of space.

Solution

To solve the problem, we can use the following algorithmic approach:

  1. Convert the number to a string to easily access each digit.
  2. Traverse the digits from left to right to find the first pair where the left digit is greater than the right digit.
  3. Once a violation is found, decrease the left digit by 1 and set all subsequent digits to '9' to ensure the result is the largest possible number with monotone increasing digits.
  4. Finally, convert the modified string back to an integer and return it.

Code Solutions

def monotoneIncreasingDigits(n: int) -> int:
    s = str(n)
    length = len(s)
    # Convert string to list for easy manipulation
    digits = list(s)
    
    # Find the first position where the monotonicity is broken
    for i in range(length - 1):
        if digits[i] > digits[i + 1]:
            # Decrease the digit at position i
            digits[i] = str(int(digits[i]) - 1)
            # Set all subsequent digits to '9'
            digits[i + 1:] = ['9'] * (length - i - 1)
            break
            
    # Convert back to string and remove any leading '0's if necessary
    return int(''.join(digits))
← Back to All Questions