An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.
Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.
Example 1:
Input: n = 10 Output: 9
Example 2:
Input: n = 1234 Output: 1234
Example 3:
Input: n = 332 Output: 299
Constraints:
0 <= n <= 109When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The core idea behind the brute force approach is to check every number smaller than the given input number. For each of these smaller numbers, we check if its digits are in non-decreasing order. We stop when we find the largest number that satisfies the condition.
Here's how the algorithm would work step-by-step:
def monotone_increasing_digits_brute_force(number):
current_number = number - 1
while current_number >= 0:
number_string = str(current_number)
is_monotone = True
# Check if digits are in non-decreasing order.
for index in range(len(number_string) - 1):
if int(number_string[index]) > int(number_string[index + 1]):
is_monotone = False
break
# If the number is monotone, return it
if is_monotone:
return current_number
# Decrement if not monotone and try again
current_number -= 1
return 0The key idea is to find the point where the digits stop being in increasing order from left to right. Then, we decrease the digit at that point and adjust the rest of the number to be as large as possible while still maintaining the increasing order.
Here's how the algorithm would work step-by-step:
def monotoneIncreasingDigits(number):
number_string = list(str(number))
number_length = len(number_string)
inflection_point_index = number_length
for i in range(number_length - 1):
if number_string[i] > number_string[i + 1]:
inflection_point_index = i
break
# Find where the increasing pattern breaks.
if inflection_point_index < number_length:
while inflection_point_index > 0 and number_string[inflection_point_index - 1] == number_string[inflection_point_index]:
inflection_point_index -= 1
number_string[inflection_point_index] = str(int(number_string[inflection_point_index]) - 1)
# Maximize remaining digits to maintain the monotone property.
for i in range(inflection_point_index + 1, number_length):
number_string[i] = '9'
return int("".join(number_string))| Case | How to Handle |
|---|---|
| Input is 0 | Return 0 since it is already monotone increasing. |
| Input is a single digit number (1-9) | Return the number itself, as it trivially satisfies the condition. |
| Input is already monotone increasing (e.g., 12345) | Return the number itself without modification. |
| Input contains a long sequence of 9s (e.g., 3329999) | Decrement the digit before the 9s and change all trailing digits to 9, potentially requiring cascading decrements. |
| Input has a large number of digits causing potential integer overflow during intermediate calculations. | Use string manipulation to represent the number and avoid integer overflow. |
| Input starts with a descending pair (e.g., 321) | Requires decrementing the leading digit and setting the rest to 9s. |
| Input resulting in 0 after decrementing (e.g. 100), should return 99 | Handle the special case that the final result can be made up of all nines. |
| The input is the maximum possible integer value | String conversion will allow algorithm to run, and will be automatically monotone since all digits will be largest possible. |