LeetCode 738: Monotone Increasing Digits

Problem Description

LeetCode Problem 738

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

Difficulty: Medium

Tags: math, greedy

Rating: 92.57%

Intuition

The key insight to solving this problem is to find the first point where the monotone increasing property is violated (where a digit is smaller than the previous digit), and then modify the number to get the largest possible monotone increasing number less than or equal to the input.

Solution Walkthrough

Let’s break down the solution with a detailed example using n = 332:

1. First, we convert the number to a list of characters: ['3', '3', '2']

2. We scan from left to right to find where the monotone increasing property is violated:

   • Compare 3 and 3: okay (equal)
   • Compare 3 and 2: violation found! (3 > 2)

3. When we find a violation, we:

   • Decrease the previous digit (3 becomes 2)
   • Set all following digits to 9
   • Result: 299

Here’s a visualization of the process:

332 (initial number)
↓
322 (after decreasing the first '3')
↓
299 (after setting remaining digits to '9')

Another example with n = 1234:

• Since all digits are already increasing (1 < 2 < 3 < 4), no modifications are needed.

Let’s look at a more complex example, n = 668841:

668841 (initial number)
↓
668841 -> 668741 -> 667741 (8 > 4, decrease 8; 8 > 7, decrease 8)
↓
667741 -> 667799 (Set all remaining digits to 9)

Python Implementation

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = list(str(n))
        # Find the first decreasing digit
        i = 1
        while i < len(s) and s[i-1] <= s[i]:
            i += 1
        
        # Decrease the previous digit 
        while i > 0 and i < len(s) and s[i-1] > s[i]:
            s[i-1] = str(int(s[i-1]) - 1)
            i -= 1
            
        # Set all digits after the first decreasing digit to 9
        for j in range(i + 1, len(s)):
            s[j] = '9'
    
        return int(''.join(s))

Time and Space Complexity

• Time Complexity: $O(n)$, where n is the number of digits in the input number. We may need to scan through all digits once.
• Space Complexity: $O(log n)$ to store the digits of the number. Since we convert the number to a string, we need space proportional to the number of digits.