algoadvance

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

Monotone increasing digits mean that for any given number, each digit is less than or equal to the one that comes after it.

Example 1:

Input: N = 10
Output: 9

Example 2:

Input: N = 1234
Output: 1234

Example 3:

Input: N = 332
Output: 299

Clarifying Questions

  1. Can N be zero? (Yes, 0 is a valid input.)
  2. Is N allowed to be extremely large? (For our purposes, assume N fits within standard 32-bit integer limits.)

Strategy

The primary strategy to solve this problem is to iterate from right to left (i.e., from the least significant digit to the most significant digit) and find the first place where the digits are not in a monotone increasing order. When such a place is found, decrement the value at the previous place, and set all subsequent digits to 9 to get the largest possible value less than or equal to the given number N with monotone increasing digits.

Steps:

  1. Convert the integer N to a list of its digits.
  2. Traverse the list starting from the second last digit.
  3. If a digit is greater than the next one, decrement this digit and mark everything to the right as 9.
  4. Once the entire digit list is processed and corrected, convert it back to an integer and return.

Code

def monotoneIncreasingDigits(N: int) -> int:
    digits = list(map(int, str(N)))
    n = len(digits)
    
    # Step 1: Find the first occurrence from right where digits are not in increasing order
    marker = n
    for i in range(n - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            marker = i
            digits[i - 1] -= 1
    
    # Step 2: Set all digits to the right of marker to 9
    for i in range(marker, n):
        digits[i] = 9
    
    return int("".join(map(str, digits)))

# Test cases
print(monotoneIncreasingDigits(10))    # Output: 9
print(monotoneIncreasingDigits(1234))  # Output: 1234
print(monotoneIncreasingDigits(332))   # Output: 299

Time Complexity

The time complexity of this solution is O(n), where n is the number of digits in N. This is because we traverse the list of digits a few times but in a linear fashion, therefore maintaining an overall linear time complexity.

This solution ensures that we efficiently correct the digits by checking from the least significant to the most significant digit and making necessary adjustments.

Try our interview co-pilot at AlgoAdvance.com