#738

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Monotone Increasing Digits

Determine the largest number less than or equal to n with digits in non-decreasing order using a greedy, invariant-driven approach.

math greedy

Problem Statement

Given a non-negative integer n, find the largest integer less than or equal to n such that its digits are in non-decreasing order. A number is monotone increasing if for every pair of adjacent digits x and y, x ≤ y holds.

For example, given n = 332, the largest monotone increasing number less than or equal to n is 299. Your solution must handle values up to 10^9 efficiently and account for digit adjustments that preserve the invariant without overshooting.

Examples

Example 1

Input: n = 10

Output: 9

Example details omitted.

Example 2

Input: n = 1234

Output: 1234

Example details omitted.

Example 3

Input: n = 332

Output: 299

Example details omitted.

Constraints

0 <= n <= 109

Solution Approach

Convert n to a digit array

Represent n as an array of its digits to allow easy access and manipulation. This enables scanning from left to right to detect any violation of the monotone increasing property.

Greedy digit correction

Iterate from left to right, and when a digit is greater than the next, decrement it and set all subsequent digits to 9. This ensures the invariant holds and the number remains maximal.

Reassemble the result

After adjustments, convert the digit array back to an integer. Leading digits remain unchanged unless decremented, preserving the largest possible monotone increasing number.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) because each digit is processed once, and space complexity is O(log n) to store the digits in an array representation of n.

What Interviewers Usually Probe

Asks about handling digit violations and the greedy invariant.
Checks if you understand why setting trailing digits to 9 maximizes the number.
Looks for a clear explanation of digit-by-digit adjustments without overshooting n.

Common Pitfalls or Variants

Common pitfalls

Forgetting to set all digits after a decrement to 9, breaking maximality.
Misidentifying which digit to decrement when multiple violations exist.
Attempting a brute-force scan of all numbers ≤ n instead of a greedy digit approach.

Follow-up variants

Find the smallest monotone decreasing number ≥ n.
Compute the count of monotone increasing numbers ≤ n.
Modify the approach to work with a custom base instead of decimal digits.

FAQ

What defines a monotone increasing digit sequence?

A number is monotone increasing if every digit is less than or equal to its right neighbor.

How do I handle numbers like 332 in this problem?

Detect the violation at the first decreasing pair, decrement the left digit, and set all following digits to 9, yielding 299.

Why is the greedy approach optimal here?

Because adjusting digits from left to right ensures maximality while preserving the monotone invariant.

Can this method handle n up to 10^9 efficiently?

Yes, it processes each digit only once, so the time and space complexity is O(log n).

Does GhostInterview help explain the invariant plus greedy pattern?

Yes, it walks through detecting violations and applying greedy corrections step by step for maximal results.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = list(str(n))
        i = 1
        while i < len(s) and s[i - 1] <= s[i]:
            i += 1
        if i < len(s):
            while i and s[i - 1] > s[i]:
                s[i - 1] = str(int(s[i - 1]) - 1)
                i -= 1
            i += 1
            while i < len(s):
                s[i] = '9'
                i += 1
        return int(''.join(s))

Continue Practicing

#781 rabbits in forest #670 maximum swap #910 smallest range ii