Monotone Increasing Digits

📋

Problem

Imagine you have a number displayed on a digital screen, but the digits must never decrease from left to right. If the number doesn't meet this rule, you want to find the largest number less than or equal to it that does.

Given a non-negative integer n, find the largest number less than or equal to n with monotone increasing digits. A number has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

0 <= n <= 10^9

Edge cases: n = 0 → 0 (smallest number)n = 10 → 9 (single digit fallback)n = 111111111 → 111111111 (all digits same)

</>

IDE

def monotoneIncreasingDigits(n: int) -> int:public int monotoneIncreasingDigits(int n)int monotoneIncreasingDigits(int n)function monotoneIncreasingDigits(n)

def monotoneIncreasingDigits(n: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int monotoneIncreasingDigits(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int monotoneIncreasingDigits(int n) {
    // Write your solution here
    return 0;
}

function monotoneIncreasingDigits(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 332Not adjusting digits when input is not monotone increasing.✅ Implement a right-to-left scan to detect decreases and adjust digits accordingly.

Wrong: 10Returning input without checking monotonicity or adjusting digits.✅ Check for monotonicity and decrement digits when violation found, setting trailing digits to 9.

Wrong: 1000Failing to handle leading zeros after decrementing the first digit.✅ After decrementing a digit, set all trailing digits to 9 to avoid leading zeros.

Wrong: 2999Fixing only first violation without propagating decrements leftwards.✅ Iterate leftwards repeatedly until all digits are monotone increasing.

Wrong: 1234321Off-by-one error in decrementing digit or setting trailing digits.✅ Decrement digit at violation index and set all digits to the right to 9.

✓

Test Cases

Focus on handling smallest and simplest inputs correctly before tackling edge cases.

Ensure your greedy logic handles multiple decrements and tricky digit patterns.

Optimize your solution to run in linear time relative to the number of digits.

t1_01basic

Input{"n":332}

Expected299

⏱ Performance - must finish in 2000ms

332 is not monotone increasing because 3 > 2. The largest monotone increasing number less than or equal to 332 is 299.

💡 Consider scanning digits from right to left to detect decreases.

💡 Use a greedy approach to fix digits when a decrease is found.

💡 Decrease the digit causing the violation and set all following digits to 9.

Why it failed: Output incorrect: likely not handling digit decreases properly. Fix by scanning right to left and adjusting digits to maintain monotonicity.

✓ Correctly identifies and adjusts digits to produce the largest monotone increasing number.

t1_02basic

Input{"n":1234}

Expected1234

⏱ Performance - must finish in 2000ms

1234 is already monotone increasing, so the output is the same as input.

💡 Check if the input number is already monotone increasing.

💡 If no decreases found, return the number as is.

💡 Avoid unnecessary digit modifications when input is valid.

Why it failed: Incorrectly modifies a number that is already monotone increasing. Fix by verifying monotonicity before changes.

✓ Correctly returns input when it is already monotone increasing.

t2_01edge

Input{"n":0}

Expected0

⏱ Performance - must finish in 2000ms

0 is the smallest number and is monotone increasing by definition.

💡 Consider the smallest input value and its properties.

💡 Check if your code handles zero without errors.

💡 Return zero immediately if input is zero.

Why it failed: Fails on zero input, possibly due to missing base case. Add explicit check for n=0.

✓ Handles zero input correctly as monotone increasing.

t2_02edge

Input{"n":10}

Expected9

⏱ Performance - must finish in 2000ms

10 is not monotone increasing because 1 > 0. The largest monotone increasing number less than or equal to 10 is 9.

💡 Check how your code handles two-digit numbers with a decrease.

💡 Ensure digits after the decrease are set to 9.

💡 Decrease the digit causing the violation by one.

Why it failed: Fails to adjust digits correctly for two-digit numbers. Fix by decrementing the violating digit and setting trailing digits to 9.

✓ Correctly adjusts two-digit numbers with decreases.

t2_03edge

Input{"n":111111111}

Expected111111111

⏱ Performance - must finish in 2000ms

All digits are the same, so the number is already monotone increasing.

💡 Test if your code handles numbers with all identical digits.

💡 Such numbers should be returned as is.

💡 Avoid unnecessary digit changes when digits are equal.

Why it failed: Incorrectly modifies numbers with all identical digits. Fix by checking for monotonicity including equality.

✓ Correctly returns numbers with all identical digits unchanged.

t3_01corner

Input{"n":1000}

Expected999

⏱ Performance - must finish in 2000ms

1000 is not monotone increasing because 1 > 0 after the first digit. The largest monotone increasing number less than or equal to 1000 is 999.

💡 Check how your code handles leading zeros after adjustment.

💡 When decreasing a digit, ensure all following digits become 9.

💡 Handle cases where the first digit decreases and affects the entire number.

Why it failed: Fails to handle leading zeros after decrementing the first digit. Fix by setting all trailing digits to 9 after decrement.

✓ Correctly handles leading zeros by converting them to 9s after decrement.

t3_02corner

Input{"n":3321}

Expected2999

⏱ Performance - must finish in 2000ms

3321 is not monotone increasing; the largest monotone increasing number less than or equal to it is 2999.

💡 Beware of greedy traps that only fix the first violation.

💡 You may need to propagate decrements leftwards multiple times.

💡 Repeat decrement and set trailing digits to 9 until monotone.

Why it failed: Fails greedy trap by fixing only first violation without rechecking earlier digits. Fix by iterating leftwards until monotone.

✓ Correctly propagates decrements leftwards to ensure monotonicity.

t3_03corner

Input{"n":1234321}

Expected1233999

⏱ Performance - must finish in 2000ms

1234321 is not monotone increasing; the largest monotone increasing number less than or equal to it is 1233999.

💡 Check for off-by-one errors in digit decrementing.

💡 Ensure you decrement the correct digit and set all right digits to 9.

💡 Verify that after decrement, the number is monotone increasing.

Why it failed: Off-by-one error in decrementing digit or setting trailing digits. Fix by decrementing digit at violation index and setting all right digits to 9.

✓ Correctly handles off-by-one decrements and trailing 9s.

t4_01performance

Input{"n":999999999}

Expectednull

⏱ Performance - must finish in 2000ms

Input n=999999999 tests performance on maximum 9-digit input. Algorithm must run in O(d) time where d=9.

💡 Brute force checking all numbers downwards will time out.

💡 Use a greedy right-to-left digit adjustment approach.

💡 Avoid enumerating all numbers; work directly on digit array.

Why it failed: TLE due to brute force approach with O(n) complexity. Fix by implementing O(d) greedy digit adjustment.

✓ Efficient O(d) solution passes within time limit.

Practice

1. You are given a list of non-negative integers and need to arrange them to form the largest possible number when concatenated. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic Programming to find the maximum concatenation by exploring all subsequences

B. Sorting the numbers as strings using a custom comparator that compares concatenations

C. Greedy approach by always picking the largest integer first

D. Brute force generating all permutations and selecting the maximum concatenation

Solution

1. Step 1: Understand the problem requires ordering numbers to maximize concatenation

   The key is to compare pairs by concatenating in both possible orders and deciding which order yields a larger combined string.

2. Step 2: Recognize that sorting with a custom comparator based on concatenation comparisons guarantees optimal order

   This approach ensures the final concatenation is lexicographically largest, unlike greedy or DP which do not handle pairwise ordering correctly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Custom comparator sorting is the standard solution for this problem [OK]

Hint: Compare concatenations as strings to decide order [OK]

Common Mistakes:

• Assuming greedy pick of largest integer works
• Using DP which is unnecessary
• Brute force is correct but inefficient

2. Consider the following Python code for forming the largest number from the list [3, 30, 34, 5]. What is the final returned string?

easy

A. 534330

B. 53430

C. 534303

D. 534330

Solution

1. Step 1: Convert numbers to strings: ['3', '30', '34', '5']

   We compare pairs by concatenation: '5'+'34' vs '34'+'5' -> '534' > '345', so '5' before '34'. Similarly for others.

2. Step 2: Sort using custom comparator to get order: ['5', '34', '3', '30']

   Concatenate to get '534330'. The check for leading zero is false since first is '5'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Concatenation order matches expected largest number [OK]

Hint: Compare concatenations 'a+b' and 'b+a' to order strings [OK]

Common Mistakes:

• Off-by-one in sorting
• Ignoring leading zero case
• Misordering '30' and '3'

3. Given the following code for partitioning labels, what is the returned list when the input string is "eccbbbbdec"?

def partitionLabels(s):
    last = [0] * 26
    for i, c in enumerate(s):
        last[ord(c) - ord('a')] = i
    res = []
    start = 0
    end = 0
    for i, c in enumerate(s):
        end = max(end, last[ord(c) - ord('a')])
        if i == end:
            res.append(end - start + 1)
            start = i + 1
    return res

easy

A. [10]

B. [9, 1]

C. [1, 9]

D. [3, 7]

Solution

1. Step 1: Compute last occurrences

   Characters: e last at 8, c last at 9, b last at 6, d last at 7.

2. Step 2: Trace partitions

   Start=0, end=0 initially. Iterate: - i=0 (e): end=max(0,8)=8 - i=1 (c): end=max(8,9)=9 - i=2 (c): end=9 - i=3 (b): end=max(9,6)=9 - i=4 (b): end=9 - i=5 (b): end=9 - i=6 (b): end=9 - i=7 (d): end=max(9,7)=9 - i=8 (e): end=9 - i=9 (c): i==end, partition size=9-0+1=10 Append 10, start=10 (end of string) But since string length is 10, only one partition of size 10. However, careful: last occurrence of 'e' is 8, 'c' is 9, so partition ends at 9. So only one partition of size 10.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Partition covers entire string length 10 [OK]

Hint: Track max last occurrence to find partition end [OK]

Common Mistakes:

• Miscounting partition size by off-by-one
• Stopping partition too early ignoring max last occurrence
• Confusing character indices

4. What is the time complexity of the optimal min-heap based algorithm for finding the minimum number of platforms required for n trains?

medium

A. O(n²) due to nested loops checking all train pairs

B. O(n) because each train is processed once

C. O(n log n) due to sorting and heap operations for each train

D. O(n log k) where k is the maximum number of platforms needed

Solution

1. Step 1: Identify sorting cost

   Sorting n trains by arrival time costs O(n log n).

2. Step 2: Analyze heap operations

   Each train causes at most one push and one pop on the heap, each O(log n), so total O(n log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + heap operations dominate complexity [OK]

Hint: Sorting + heap push/pop per train -> O(n log n) [OK]

Common Mistakes:

• Assuming O(n) ignoring sorting and heap costs
• Confusing heap size k with n for complexity
• Mistaking nested loops for optimal approach complexity

5. Suppose now each cookie can be assigned to multiple children (reusable cookies). Which modification to the original greedy algorithm correctly computes the maximum number of content children?

hard

A. Sort both arrays and increment both pointers i and j on assignment as before

B. Use the brute force nested loops approach to try all assignments since greedy fails with reusable cookies

C. Sort greed array only and assign the largest cookie to each child without sorting cookies

D. Keep sorting arrays, but do not increment cookie pointer j when a cookie is assigned; only increment child pointer i

Solution

1. Step 1: Understand reuse effect

   Cookies can be assigned multiple times, so cookie pointer j should not advance on assignment.

2. Step 2: Modify greedy accordingly

   Keep sorting both arrays, but only increment child pointer i when a cookie satisfies a child; j stays to reuse the same cookie.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Not incrementing j allows cookie reuse [OK]

Hint: Do not advance cookie pointer on assignment for reuse [OK]

Common Mistakes:

• Incrementing both pointers breaks reuse
• Using brute force unnecessarily
• Ignoring sorting leads to suboptimal matches