Find the Largest Monotone Increasing Number

Question

The candidate is asked to write a function that finds the largest monotone increasing number less than or equal to a given number.

Codemia · Accepted Answer

To find the largest monotone increasing number less than or equal to a given number, we can start by converting the number into a string to analyze its digits. We will iterate through the digits from left to right and identify the first position where the digits stop being monotone increasing. Once we find that position, we can decrement the digit at that position and set all subsequent digits to '9' to ensure the largest possible number that remains monotone increasing.

1. Convert the number to a string to easily access each digit.
2. Initialize a variable to track the position where the digits stop being monotone increasing.
3. Iterate through the digits:
   - If the current digit is greater than the next digit, mark the position.
   - Decrement the digit at the marked position by 1.
   - Change all subsequent digits to '9'.
4. Convert the modified string back to an integer and return it.

The time complexity of this solution is O(n), where n is the number of digits in the input number. This is because we may need to iterate through all the digits to find the point of decrease. The space complexity is O(n) as well, due to the storage of the string representation of the number.

```python
def largest_monotone_increasing_number(n: int) -> int:
    num_str = list(str(n))
    length = len(num_str)
    marker = length

for i in range(length - 1):
        if num_str[i] > num_str[i + 1]:
            marker = i
            num_str[i] = str(int(num_str[i]) - 1)
            for j in range(i + 1, length):
                num_str[j] = '9'
            break

return int(''.join(num_str[:marker]))
```
This code defines a function that implements the outlined approach and returns the largest monotone increasing number.

It's important to consider edge cases such as single-digit numbers, where the number itself is already the largest monotone increasing number. Additionally, we should handle cases where the input number is already monotone increasing, in which case we simply return it as is.

Find the Largest Monotone Increasing Number

Google

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string