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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Monotone Increasing Digits

Number: 738

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer n, find the largest number that is less than or equal to n such that its digits are monotone increasing (each digit is less than or equal to the next digit).

Key Insights

  • Convert the integer into a list (or array) of digits to easily inspect and modify individual digits.
  • Identify the first instance (from right to left) where a digit is smaller than the digit preceding it.
  • Once a violation is found, decrement the violating digit (the digit before the break) and set all subsequent digits to 9 to maximize the number.
  • The process might require backtracking if multiple violations exist consecutively.

Space and Time Complexity

Time Complexity: O(d) where d is the number of digits in n, typically at most 10. Space Complexity: O(d) for storing the digits.

Solution

The solution utilizes a greedy strategy. By converting the number into a list of its digits, we traverse from the end towards the beginning. When we detect that a previous digit is greater than the current digit, we decrement that digit and mark the position. Then, all digits to the right of this marker are changed to 9. This ensures that the new number remains as large as possible while satisfying the monotone increasing property.

Data Structures: List/array for digits. Algorithm: Greedy traversal and backtracking adjustment.

Code Solutions

# Convert the integer to a list of its digit characters
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        digits = list(str(n))  # List of digit characters
        marker = len(digits)   # Marker to indicate where digits need to be replaced with '9'
        # Traverse from right to left
        for i in range(len(digits) - 1, 0, -1):
            # If the digit on the left is greater than the current digit
            if digits[i - 1] > digits[i]:
                # Decrement that digit by 1
                digits[i - 1] = str(int(digits[i - 1]) - 1)
                marker = i  # Update marker position
        # Set all digits after the marker to '9'
        for i in range(marker, len(digits)):
            digits[i] = '9'
        return int("".join(digits))
← Back to All Questions