Monotone Increasing Digits

🎯

Monotone Increasing Digits

mediumGREEDYAmazonGoogle

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.

💡 This problem asks you to adjust a number's digits so they never decrease from left to right. Beginners often struggle because it involves careful digit manipulation and understanding how to 'fix' the number from right to left to maintain the monotone property.

📋

Problem Statement

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

💡

Example

Input"n = 332"

Output299

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

Input"n = 1234"

Output1234

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

• n = 0 → 0 (smallest number)
• n = 10 → 9 (single digit fallback)
• n = 111111111 → 111111111 (all digits same)
• n = 1000 → 999 (leading zeros after adjustment)

⚠️

Common Mistakes

Not resetting digits after decrement to 9

Returns a smaller number than necessary, missing the largest monotone number

✅ After decrementing a digit, set all digits to the right to 9

Decrementing digits without checking previous digits again

May leave the number non-monotone if multiple decrements needed

✅ Iterate backwards until no monotone violation remains

Converting digits back to integer before fixing all digits

Leads to incorrect final number or runtime errors

✅ Only convert back after all digit adjustments are done

Ignoring edge cases like n=0 or all digits equal

Incorrect output or unnecessary changes

✅ Add checks or ensure algorithm naturally handles these cases

🧠

Brute Force (Check All Numbers Downwards)

💡 This approach exists to build intuition by trying all numbers less than or equal to n until we find one that is monotone increasing. It is simple but inefficient, helping beginners understand the problem constraints and monotone property.

Intuition

Start from n and decrement by 1, checking each number if its digits are monotone increasing. The first such number found is the answer.

Algorithm

1. Start from n and go downwards to 0.
2. For each number, check if its digits are monotone increasing.
3. If yes, return that number as the answer.
4. If no, continue decrementing.

💡 The difficulty is in realizing that checking monotonicity is easy, but iterating downwards is costly and impractical for large n.

</>

Code

def monotoneIncreasingDigits(n: int) -> int:
    def is_monotone(num: int) -> bool:
        prev = 10
        while num > 0:
            digit = num % 10
            if digit > prev:
                return False
            prev = digit
            num //= 10
        return True

    for x in range(n, -1, -1):
        if is_monotone(x):
            return x

# Driver code
if __name__ == '__main__':
    print(monotoneIncreasingDigits(332))  # Expected: 299

Line Notes

def is_monotone(num: int) -> bool:Helper function to check if digits are monotone increasing

prev = 10Initialize prev to 10, larger than any digit, to compare first digit

if digit > prev:If current digit is greater than previous digit (from right to left), monotone property violated

for x in range(n, -1, -1):Iterate downwards from n to 0 to find the largest monotone number

public class Solution {
    public static boolean isMonotone(int num) {
        int prev = 10;
        while (num > 0) {
            int digit = num % 10;
            if (digit > prev) return false;
            prev = digit;
            num /= 10;
        }
        return true;
    }

    public static int monotoneIncreasingDigits(int n) {
        for (int x = n; x >= 0; x--) {
            if (isMonotone(x)) return x;
        }
        return 0;
    }

    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits(332)); // Expected: 299
    }
}

Line Notes

public static boolean isMonotone(int num) {Helper method to check monotone increasing digits

int prev = 10;Initialize prev to 10 to compare digits from right to left

if (digit > prev) return false;If current digit is greater than previous digit, monotone property fails

for (int x = n; x >= 0; x--) {Decrement from n to 0 to find the largest monotone number

#include <iostream>
using namespace std;

bool isMonotone(int num) {
    int prev = 10;
    while (num > 0) {
        int digit = num % 10;
        if (digit > prev) return false;
        prev = digit;
        num /= 10;
    }
    return true;
}

int monotoneIncreasingDigits(int n) {
    for (int x = n; x >= 0; x--) {
        if (isMonotone(x)) return x;
    }
    return 0;
}

int main() {
    cout << monotoneIncreasingDigits(332) << endl; // Expected: 299
    return 0;
}

Line Notes

bool isMonotone(int num) {Helper function to check monotone increasing digits

int prev = 10;Initialize prev to 10 to compare digits from right to left

if (digit > prev) return false;If current digit is greater than previous digit, monotone property fails

for (int x = n; x >= 0; x--) {Iterate downwards from n to 0 to find the largest monotone number

function isMonotone(num) {
    let prev = 10;
    while (num > 0) {
        let digit = num % 10;
        if (digit > prev) return false;
        prev = digit;
        num = Math.floor(num / 10);
    }
    return true;
}

function monotoneIncreasingDigits(n) {
    for (let x = n; x >= 0; x--) {
        if (isMonotone(x)) return x;
    }
    return 0;
}

// Test
console.log(monotoneIncreasingDigits(332)); // Expected: 299

Line Notes

function isMonotone(num) {Helper function to check if digits are monotone increasing

let prev = 10;Initialize prev to 10 to compare digits from right to left

if (digit > prev) return false;If current digit is greater than previous digit, monotone property fails

for (let x = n; x >= 0; x--) {Decrement from n to 0 to find the largest monotone number

⏱

Complexity

TimeO(n * d) where d is number of digits in n

SpaceO(1)

In worst case, we check every number from n down to 0, and for each number, we check its digits (d digits).

💡 For n=1000, this means up to 1000 checks, each checking up to 4 digits, which is 4000 operations - too slow for large n.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and monotone checking.

🧠

Greedy Right-to-Left Fix with Digit Array

💡 This approach exists to efficiently fix the number by scanning digits from right to left and adjusting digits to maintain monotone increasing property. It introduces the key greedy insight.

Intuition

Convert the number to a digit array, scan from right to left, and whenever a digit is greater than the next digit, decrement it and set all digits to the right to 9.

Algorithm

1. Convert n to a list of digits.
2. Traverse digits from right to left.
3. If a digit is greater than the next digit, decrement it by 1 and set all digits to the right to 9.
4. Repeat until all digits are monotone increasing.
5. Convert the digit list back to an integer and return.

💡 The tricky part is realizing that after decrementing a digit, you must reset all digits to the right to 9 to maximize the number.

</>

Code

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    i = len(digits) - 1
    while i > 0 and digits[i - 1] <= digits[i]:
        i -= 1
    if i == 0:
        return n
    while i > 0 and digits[i - 1] > digits[i]:
        digits[i - 1] -= 1
        for j in range(i, len(digits)):
            digits[j] = 9
        i -= 1
    return int(''.join(map(str, digits)))

# Driver code
if __name__ == '__main__':
    print(monotoneIncreasingDigits(332))  # Expected: 299

Line Notes

digits = list(map(int, str(n)))Convert number to list of digits for easy manipulation

while i > 0 and digits[i - 1] <= digits[i]:Find first position from right where monotone property breaks

digits[i - 1] -= 1Decrement the digit that breaks monotone property to fix violation

for j in range(i, len(digits)): digits[j] = 9Set all digits to the right to 9 to maximize the number after decrement

public class Solution {
    public static int monotoneIncreasingDigits(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int i = digits.length - 1;
        while (i > 0 && digits[i - 1] <= digits[i]) {
            i--;
        }
        if (i == 0) return n;
        while (i > 0 && digits[i - 1] > digits[i]) {
            digits[i - 1]--;
            for (int j = i; j < digits.length; j++) {
                digits[j] = '9';
            }
            i--;
        }
        return Integer.parseInt(new String(digits));
    }

    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits(332)); // Expected: 299
    }
}

Line Notes

char[] digits = Integer.toString(n).toCharArray();Convert number to char array for digit manipulation

while (i > 0 && digits[i - 1] <= digits[i]) {Find first index from right where monotone property breaks

digits[i - 1]--;Decrement the digit that breaks monotone property to fix violation

for (int j = i; j < digits.length; j++) { digits[j] = '9'; }Set all digits to the right to '9' to maximize the number after decrement

#include <iostream>
#include <string>
using namespace std;

int monotoneIncreasingDigits(int n) {
    string digits = to_string(n);
    int i = digits.size() - 1;
    while (i > 0 && digits[i - 1] <= digits[i]) {
        i--;
    }
    if (i == 0) return n;
    while (i > 0 && digits[i - 1] > digits[i]) {
        digits[i - 1]--;
        for (int j = i; j < digits.size(); j++) {
            digits[j] = '9';
        }
        i--;
    }
    return stoi(digits);
}

int main() {
    cout << monotoneIncreasingDigits(332) << endl; // Expected: 299
    return 0;
}

Line Notes

string digits = to_string(n);Convert number to string for digit manipulation

while (i > 0 && digits[i - 1] <= digits[i]) {Find first index from right where monotone property breaks

digits[i - 1]--;Decrement the digit that breaks monotone property to fix violation

for (int j = i; j < digits.size(); j++) { digits[j] = '9'; }Set all digits to the right to '9' to maximize the number after decrement

function monotoneIncreasingDigits(n) {
    let digits = n.toString().split('').map(Number);
    let i = digits.length - 1;
    while (i > 0 && digits[i - 1] <= digits[i]) {
        i--;
    }
    if (i === 0) return n;
    while (i > 0 && digits[i - 1] > digits[i]) {
        digits[i - 1]--;
        for (let j = i; j < digits.length; j++) {
            digits[j] = 9;
        }
        i--;
    }
    return parseInt(digits.join(''), 10);
}

// Test
console.log(monotoneIncreasingDigits(332)); // Expected: 299

Line Notes

let digits = n.toString().split('').map(Number);Convert number to array of digits for manipulation

while (i > 0 && digits[i - 1] <= digits[i]) {Find first index from right where monotone property breaks

digits[i - 1]--;Decrement the digit that breaks monotone property to fix violation

for (let j = i; j < digits.length; j++) { digits[j] = 9; }Set all digits to the right to 9 to maximize the number after decrement

⏱

Complexity

TimeO(d) where d is number of digits in n

SpaceO(d) for digit array

We scan the digits at most twice, and modify digits in place, so linear in number of digits.

💡 For n up to 10^9, d is at most 10, so this is very efficient.

Interview Verdict: Accepted

This approach is efficient and practical for interview coding.

🧠

Greedy with Single Pass and Marker

💡 This approach refines the previous by using a marker to track where to start setting digits to 9, making the code cleaner and easier to understand.

Intuition

Scan digits from left to right, and when a digit is less than the previous, decrement the previous digit and mark the position to set all subsequent digits to 9.

Algorithm

1. Convert n to a list of digits.
2. Traverse digits from left to right to find where monotone breaks.
3. When found, decrement the digit before the break and mark that position.
4. Set all digits after the marker to 9.
5. Convert the digit list back to integer and return.

💡 The key insight is to track the position where digits need to be fixed and then apply the fix in one pass.

</>

Code

def monotoneIncreasingDigits(n: int) -> int:
    digits = list(map(int, str(n)))
    marker = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i] < digits[i - 1]:
            digits[i - 1] -= 1
            marker = i
    for i in range(marker, len(digits)):
        digits[i] = 9
    return int(''.join(map(str, digits)))

# Driver code
if __name__ == '__main__':
    print(monotoneIncreasingDigits(332))  # Expected: 299

Line Notes

marker = len(digits)Initialize marker to length, meaning no fix needed initially

for i in range(len(digits) - 1, 0, -1):Scan digits from right to left to find where monotone breaks

digits[i - 1] -= 1Decrement the digit before the break to fix monotone property

for i in range(marker, len(digits)): digits[i] = 9Set all digits after marker to 9 to maximize the number

public class Solution {
    public static int monotoneIncreasingDigits(int n) {
        char[] digits = Integer.toString(n).toCharArray();
        int marker = digits.length;
        for (int i = digits.length - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                digits[i - 1] = (char)(digits[i - 1] - 1);
                marker = i;
            }
        }
        for (int i = marker; i < digits.length; i++) {
            digits[i] = '9';
        }
        return Integer.parseInt(new String(digits));
    }

    public static void main(String[] args) {
        System.out.println(monotoneIncreasingDigits(332)); // Expected: 299
    }
}

Line Notes

int marker = digits.length;Marker initialized to length meaning no fix needed initially

for (int i = digits.length - 1; i > 0; i--) {Scan digits from right to left to find monotone break

digits[i - 1] = (char)(digits[i - 1] - 1);Decrement digit before break by converting char to int and back to char to fix monotone property

for (int i = marker; i < digits.length; i++) { digits[i] = '9'; }Set digits after marker to '9' to maximize number

#include <iostream>
#include <string>
using namespace std;

int monotoneIncreasingDigits(int n) {
    string digits = to_string(n);
    int marker = digits.size();
    for (int i = digits.size() - 1; i > 0; i--) {
        if (digits[i] < digits[i - 1]) {
            digits[i - 1] = digits[i - 1] - 1; // convert char to int and decrement
            marker = i;
        }
    }
    for (int i = marker; i < digits.size(); i++) {
        digits[i] = '9';
    }
    return stoi(digits);
}

int main() {
    cout << monotoneIncreasingDigits(332) << endl; // Expected: 299
    return 0;
}

Line Notes

int marker = digits.size();Marker initialized to size meaning no fix needed initially

for (int i = digits.size() - 1; i > 0; i--) {Scan digits from right to left to find monotone break

digits[i - 1] = digits[i - 1] - 1; // convert char to int and decrementDecrement digit before break by converting char to int and back to char to fix monotone property

for (int i = marker; i < digits.size(); i++) { digits[i] = '9'; }Set digits after marker to '9' to maximize number

function monotoneIncreasingDigits(n) {
    let digits = n.toString().split('');
    let marker = digits.length;
    for (let i = digits.length - 1; i > 0; i--) {
        if (digits[i] < digits[i - 1]) {
            digits[i - 1] = (parseInt(digits[i - 1], 10) - 1).toString();
            marker = i;
        }
    }
    for (let i = marker; i < digits.length; i++) {
        digits[i] = '9';
    }
    return parseInt(digits.join(''), 10);
}

// Test
console.log(monotoneIncreasingDigits(332)); // Expected: 299

Line Notes

let marker = digits.length;Marker initialized to length meaning no fix needed initially

for (let i = digits.length - 1; i > 0; i--) {Scan digits from right to left to find monotone break

digits[i - 1] = (parseInt(digits[i - 1], 10) - 1).toString();Decrement digit before break by converting string to number and back to string to fix monotone property

for (let i = marker; i < digits.length; i++) { digits[i] = '9'; }Set digits after marker to '9' to maximize number

⏱

Complexity

TimeO(d) where d is number of digits

SpaceO(d) for digit array

Single pass from right to left with a final pass to set 9s, linear in digits.

💡 For typical inputs, this is very fast and uses minimal extra space.

Interview Verdict: Accepted

This is a clean and efficient greedy solution suitable for interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the greedy right-to-left fix or the marker approach as they are efficient and clean. Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * d)	O(1)	No	N/A	Mention only - never code
2. Greedy Right-to-Left Fix	O(d)	O(d)	No	N/A	Code this for optimal solution
3. Greedy with Marker	O(d)	O(d)	No	N/A	Code this for clean and readable solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before coding. Start with brute force to clarify the problem, then explain the greedy insight. Practice coding the optimal approach and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force approach and why it's inefficient.Step 3: Introduce the greedy right-to-left fix approach.Step 4: Code the greedy solution carefully.Step 5: Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of digit manipulation, greedy reasoning, and ability to handle tricky edge cases like trailing nines and digit borrow.

Common Follow-ups

• What if digits must be strictly increasing? → Adjust condition to digit[i] <= digit[i-1]
• How to handle very large numbers beyond integer range? → Use string manipulation without integer conversion

💡 These follow-ups test your ability to adapt the solution to variations and large inputs.

🔍

Pattern Recognition

When to Use

1) Problem involves digits or characters with monotone or sorted property. 2) Need to find largest/smallest number under constraints. 3) Greedy fix from right to left or left to right is possible. 4) Adjust trailing digits to maximize/minimize.

Signature Phrases

'monotone increasing digits''largest number less than or equal to n''digits never decrease from left to right'

NOT This Pattern When

Sorting problems or DP problems that do not involve digit-wise greedy fixes

Similar Problems

Largest Number At Least Twice of Others - involves digit comparisons and greedy checksNon-decreasing Array - similar monotone property but on arraysFind the Smallest Divisor Given a Threshold - uses greedy and binary search

Practice

1. You have a list of tasks represented by characters, each task takes 1 unit of time to execute. The CPU must wait for at least n units of time before executing the same task again. Which approach guarantees the minimum total time to finish all tasks?

easy

A. Dynamic Programming that tries all permutations of task orders to find the minimal schedule

B. Greedy algorithm using a max-heap to always schedule the most frequent available task next

C. Simple round-robin scheduling without considering cooldown intervals

D. Sorting tasks by frequency and inserting idle slots greedily without priority queue

Solution

1. Step 1: Understand the cooldown constraint

   The CPU must wait n units before repeating the same task, so scheduling must consider task frequencies and cooldowns.

2. Step 2: Why max-heap greedy works best

   Using a max-heap prioritizes tasks with the highest remaining frequency, ensuring minimal idle time by always picking the most urgent task available.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Max-heap approach matches known optimal solution [OK]

Hint: Max-heap greedily schedules highest frequency tasks first [OK]

Common Mistakes:

• Assuming DP or brute force is needed
• Ignoring cooldown leads to incorrect minimal time
• Greedy without priority queue misses optimal order

2. Consider the following buggy code for assigning cookies to children. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 5: Missing increment of j when cookie is assigned

B. Line 3: Incorrect loop condition including count < len(g)

C. Line 1: Missing sorting of g and s arrays

D. Line 7: Incrementing j only in else block

Solution

1. Step 1: Identify missing pointer increment

   When a cookie satisfies a child (s[j] ≥ g[i]), j should increment to avoid reusing the same cookie.

2. Step 2: Check code lines

   Line 5 increments count and i but does not increment j, causing the same cookie to be assigned multiple times.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without j increment on assignment, cookie reuse occurs [OK]

Hint: Check pointer increments on both branches [OK]

Common Mistakes:

• Forgetting to sort arrays
• Incorrect loop conditions
• Not incrementing both pointers on assignment

3. What is the time complexity of the peak-valley approach for the Best Time to Buy and Sell Stock II problem, and why might some candidates incorrectly think it is higher?

medium

A. O(1) since only constant extra space is used

B. O(n^2) because of nested while loops

C. O(n log n) due to sorting or searching steps

D. O(n) because each element is visited at most twice in the loops

Solution

1. Step 1: Identify loop behavior

   Though there are nested while loops, the index i only moves forward and never revisits elements.

2. Step 2: Conclude time complexity

   Each element is processed at most twice, so total time is linear O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Index i increments monotonically through array [OK]

Hint: Index i only moves forward, no repeated visits [OK]

Common Mistakes:

• Assuming nested loops multiply to O(n^2)
• Confusing space complexity with time complexity
• Thinking sorting is involved

4. What is the time complexity of the optimal greedy solution for the Jump Game problem, and why is the following common misconception incorrect? Misconception: The time complexity is O(n^2) because for each index, you might check all reachable next indices.

medium

A. O(n) because the algorithm iterates through the array once, updating max reachable index

B. O(n log n) due to sorting or binary search involved in jump calculations

C. O(n^2) because each index can jump to multiple next indices

D. O(n) but with O(n) auxiliary space for memoization

Solution

1. Step 1: Identify the algorithm's iteration pattern

   The greedy solution iterates through the array once, updating a single variable maxReach without nested loops.

2. Step 2: Explain why O(n^2) is incorrect

   Unlike brute force, it does not explore all jumps explicitly; it only tracks the furthest reachable index, so no nested iteration occurs.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass through array -> O(n) time, no nested loops [OK]

Hint: Greedy uses one pass, no nested loops [OK]

Common Mistakes:

• Confusing brute force with greedy complexity
• Assuming nested loops due to jumps

5. Suppose the problem is modified so that the input list can contain negative integers as well. Which of the following approaches correctly adapts the algorithm to handle negatives and still produce the largest concatenated number?

hard

A. Convert negatives to positive strings before sorting with the comparator, then prepend '-' to those in final output

B. Filter out negative numbers since they cannot contribute to the largest concatenation

C. Separate negatives and positives, sort positives with comparator, sort negatives by absolute value descending, then concatenate positives followed by negatives

D. Convert all numbers to strings including negatives, then sort with the same comparator comparing concatenations

Solution

1. Step 1: Recognize negatives affect ordering and concatenation semantics

   Negative numbers cannot be treated the same as positives because concatenation with '-' changes lex order.

2. Step 2: Separate positives and negatives, sort positives with original comparator, sort negatives by absolute value descending

   Concatenate positives first (largest number), then negatives to maintain largest overall concatenation.

3. Step 3: This approach preserves ordering logic and handles negatives correctly

   Other options either ignore negatives or mishandle signs causing incorrect results.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Separating and sorting by sign handles negatives correctly [OK]

Hint: Negatives require separate handling, not just string comparison [OK]

Common Mistakes:

• Treating negatives as strings directly
• Ignoring negatives
• Converting negatives to positives incorrectly