Problem Description

You need to find the largest number that has monotone increasing digits and is less than or equal to a given integer n.

A number has monotone increasing digits when each digit is less than or equal to the digit that comes after it. In other words, for any two adjacent digits x and y (where x comes before y), the condition x <= y must be satisfied.

For example:

• 1234 has monotone increasing digits (1 ≤ 2 ≤ 3 ≤ 4)
• 1232 does NOT have monotone increasing digits (3 > 2 violates the rule)
• 1333 has monotone increasing digits (1 ≤ 3 ≤ 3 ≤ 3)

Given an integer n, you need to return the largest possible number that:

1. Has monotone increasing digits
2. Is less than or equal to n

For instance, if n = 1232, the answer would be 1229 because:

• 1229 has monotone increasing digits (1 ≤ 2 ≤ 2 ≤ 9)
• 1229 is the largest such number that doesn't exceed 1232

Intuition

The key insight is to scan the number from left to right and find the first position where the monotone increasing property is violated (where a digit is greater than the next digit). Once we find this violation point, we need to adjust the number to maintain the monotone property while maximizing the result.

Consider the number 1232. When we scan from left to right:

• 1 ≤ 2 ✓
• 2 ≤ 3 ✓
• 3 > 2 ✗ (violation found!)

At this violation point, we can't keep 3 because it breaks the monotone property. We need to reduce it. But simply changing 3 to 2 would give us 1222, which is not the largest possible answer.

The clever observation is: when we decrease a digit, all digits to its right can be set to 9 to maximize the result. This works because 9 is the largest digit, and any digit followed by 9 maintains the monotone property.

But there's a subtlety: sometimes we need to decrease multiple digits. For example, with 1332:

• First violation is at 3 > 2
• If we just decrease the second 3 to 2, we get 1322, but 3 > 2 is still a violation
• We need to keep decreasing backward: 1332 → 1299

The algorithm works by:

1. Finding the first violation point
2. Decreasing the violating digit and potentially propagating this decrease backward if needed
3. Setting all remaining digits to the right to 9 to maximize the result

This greedy approach ensures we get the largest possible number with monotone increasing digits that doesn't exceed n.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation converts the number to a string (character array) for easier digit manipulation, then follows these steps:

1. Find the first violation point:

   i = 1
   while i < len(s) and s[i - 1] <= s[i]:
       i += 1

   We scan from left to right, comparing each digit with the next one. The loop continues as long as the monotone property holds (s[i-1] <= s[i]). When we exit this loop, i points to the position right after the first digit that violates the monotone property.

2. Handle the violation (if found): If i < len(s), it means we found a violation. Now we need to:

   a. Decrease digits backward as needed:

   while i and s[i - 1] > s[i]:
       s[i - 1] = str(int(s[i - 1]) - 1)
       i -= 1

   Starting from the violation point, we decrease the previous digit by 1 and move backward. We continue this process while the current digit is still greater than the next digit. This handles cases like 1332 where multiple digits need to be decreased.

   b. Fill remaining positions with 9:

   i += 1
   while i < len(s):
       s[i] = '9'
       i += 1

   After adjusting the violating digits, we move forward one position (since we went backward in the previous step) and set all remaining digits to 9. This maximizes the result while maintaining the monotone property.

3. Return the result:

   return int(''.join(s))

   Convert the modified character array back to an integer.

Example walkthrough with n = 1232:

• Convert to ['1', '2', '3', '2']
• Find violation: i = 3 (because 3 > 2)
• Decrease backward: ['1', '2', '2', '2'] (decrease 3 to 2)
• Fill with 9s: ['1', '2', '2', '9']
• Result: 1229

The time complexity is O(d) where d is the number of digits, and space complexity is O(d) for storing the string representation.

Example Walkthrough

Let's trace through the algorithm with n = 1432:

Step 1: Convert to character array

• s = ['1', '4', '3', '2']

Step 2: Find the first violation point

• Start with i = 1
• Check s[0] <= s[1]: '1' <= '4' ✓, so i = 2
• Check s[1] <= s[2]: '4' <= '3' ✗ (violation found!)
• Stop with i = 2

Step 3: Handle the violation

• Since i < len(s), we found a violation at position 2

Step 3a: Decrease digits backward

• Check s[i-1] > s[i]: '4' > '3' is true
• Decrease s[1] from '4' to '3': s = ['1', '3', '3', '2']
• Move backward: i = 1
• Check s[i-1] > s[i]: '1' > '3' is false
• Stop decreasing

Step 3b: Fill remaining positions with 9

• Move forward: i = 2
• Set s[2] = '9': s = ['1', '3', '9', '2']
• Move to i = 3
• Set s[3] = '9': s = ['1', '3', '9', '9']

Step 4: Return result

• Join and convert: 1399

Verification:

• 1399 has monotone increasing digits: 1 ≤ 3 ≤ 9 ≤ 9 ✓
• 1399 ≤ 1432 ✓
• This is indeed the largest such number!

Solution Implementation

Time and Space Complexity

Time Complexity: O(d) where d is the number of digits in n.

• Converting integer n to string takes O(d) time
• The first while loop iterates through the digits once in the worst case: O(d)
• The second while loop (backtracking) can iterate at most d times: O(d)
• The third while loop fills remaining positions with '9', at most d iterations: O(d)
• Converting the result back to integer takes O(d) time
• Overall: O(d) + O(d) + O(d) + O(d) + O(d) = O(d)

Since d = log₁₀(n), the time complexity can also be expressed as O(log n).

Space Complexity: O(d) where d is the number of digits in n.

• The list s stores all digits of n, requiring O(d) space
• The string conversion and join operation create temporary strings of size O(d)
• No recursive calls or additional data structures are used
• Overall space complexity: O(d) or O(log n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Repeated Digits Before Violation

The Problem: When you encounter a violation in the monotone property, simply decreasing the digit immediately before the violation point isn't always sufficient. Consider the number 1332:

• The violation occurs at index 3 (where 3 > 2)
• If you only decrease the digit at index 2 (changing 3 to 2), you get 1322
• But 1322 still violates the monotone property because the first 3 is greater than the second 2

Why This Happens: The issue arises when there are repeated digits before the violation point. In 1332, both middle digits are 3, and when we decrease one of them, we need to also decrease the previous occurrences of the same digit.

The Solution: The code handles this with a backward loop that continues decreasing digits as long as they're greater than their next digit:

while break_point > 0 and digits[break_point - 1] > digits[break_point]:
    digits[break_point - 1] = str(int(digits[break_point - 1]) - 1)
    break_point -= 1

This ensures that for 1332:

1. First iteration: 1332 → 1322 (decrease second 3 to 2)
2. Second iteration: 1322 → 1222 (decrease first 3 to 2)
3. Now the monotone property is satisfied

Pitfall 2: Incorrect Index Management After Backtracking

The Problem: After the backward loop that decreases digits, the break_point variable has moved backward. If you forget to move it forward again before filling with 9s, you'll overwrite the wrong digits.

Why This Happens: The backward loop moves break_point to handle cascading decrements. After this loop, break_point points to the position before the last decreased digit. To correctly fill the remaining positions with 9s, you need to start from the position after the last decreased digit.

The Solution: Always increment break_point after the backward loop:

break_point += 1  # Move to the position after the last decreased digit
while break_point < length:
    digits[break_point] = '9'
    break_point += 1

Example with n = 10:

• Convert to ['1', '0']
• Violation found at index 1 (since 1 > 0)
• After backward loop: break_point = 0, digits = ['0', '0']
• Without incrementing: You'd start filling from index 0, resulting in ['9', '0'] → 90 (incorrect)
• With incrementing: You start filling from index 1, resulting in ['0', '9'] → 9 (correct, after removing leading zero)