Taro Logo

Monotone Increasing Digits

Medium
Asked by:
Profile picture
71 views
Topics:
Greedy Algorithms

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 <= 109

Solution


Clarifying Questions

When 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:

  1. What is the range of the input number `N`? Can `N` be zero or negative?
  2. If there are multiple monotone increasing numbers less than or equal to `N`, which one should I return?
  3. What is the expected output if `N` is already a monotone increasing number?
  4. By 'monotone increasing', do you mean each digit must be strictly greater than or equal to the digit to its left, or is strictly increasing required?
  5. Should the return value be an integer, or is there a different preferred output format?

Brute Force Solution

Approach

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:

  1. Start with the number that's just one less than the number you were given.
  2. Check if the digits of this number are in increasing order from left to right; that is, each digit is at least as big as the digit to its left.
  3. If the digits are in increasing order, then this is the answer! You are done.
  4. If the digits are NOT in increasing order, then reduce the number by one.
  5. Repeat steps 2-4 with the new smaller number.
  6. Keep going until you find a number where the digits are in increasing order.

Code Implementation

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 0

Big(O) Analysis

Time Complexity
O(n log n) – The outer loop iterates downwards from the input number n until a monotone increasing number is found. In the worst case, this could iterate from n down to 0, which is proportional to n. Inside the loop, there's a check to determine if the digits of the current number are monotone increasing. This digit check involves iterating through the digits of the number. The number of digits in n is proportional to log n (base 10). Therefore, the time complexity is O(n log n) since we iterate at most n times, and each time we iterate through log n digits.
Space Complexity
O(1) – The provided brute force approach iterates through numbers smaller than the input and checks the monotonicity of each number's digits. The check for monotonicity implicitly involves accessing digits of the current number, which can be done in place without creating a new data structure to store the digits. Only a few variables are needed to hold the current number being checked and possibly temporary variables for comparison within the monotonicity check, and their number doesn't depend on the size of the input number N. Thus, the space complexity is constant.

Optimal Solution

Approach

The 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:

  1. First, scan the number from left to right, looking for the first place where a digit is bigger than the digit that comes after it. This shows where the increasing pattern breaks.
  2. If you find such a spot, reduce the digit in that spot by one. This corrects the break in the sequence.
  3. After reducing the digit, replace all the digits that come after it with the digit '9'. This makes the rest of the number as large as possible while still keeping the digits in increasing order.

Code Implementation

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))

Big(O) Analysis

Time Complexity
O(n) – The algorithm iterates through the digits of the input number once to find the first decreasing digit from left to right. If a decreasing digit is found, another iteration modifies the digits after that point to '9'. Therefore, the runtime is directly proportional to the number of digits in the input number, n. This makes the time complexity O(n).
Space Complexity
O(N) – The algorithm modifies the input number by converting it to a string or character array, which takes O(N) space where N is the number of digits in the input number. After finding the breaking point, the algorithm replaces all subsequent digits with '9'. This operation is performed in-place on the string/array. Therefore, the dominant space complexity arises from the string/array representation of the number, leading to an auxiliary space usage of O(N).

Edge Cases

Input is 0
How to Handle:
Return 0 since it is already monotone increasing.
Input is a single digit number (1-9)
How to Handle:
Return the number itself, as it trivially satisfies the condition.
Input is already monotone increasing (e.g., 12345)
How to Handle:
Return the number itself without modification.
Input contains a long sequence of 9s (e.g., 3329999)
How to Handle:
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.
How to Handle:
Use string manipulation to represent the number and avoid integer overflow.
Input starts with a descending pair (e.g., 321)
How to Handle:
Requires decrementing the leading digit and setting the rest to 9s.
Input resulting in 0 after decrementing (e.g. 100), should return 99
How to Handle:
Handle the special case that the final result can be made up of all nines.
The input is the maximum possible integer value
How to Handle:
String conversion will allow algorithm to run, and will be automatically monotone since all digits will be largest possible.