Monotone Increasing Digits

Monotone Increasing Digits

What is this problem about?

The Monotone Increasing Digits problem asks you to find the largest number less than or equal to a given integer N such that each digit is non-decreasing (i.e., each digit is ≥ the digit before it). For example, 123, 1111, and 45679 are monotone increasing. This Monotone Increasing Digits interview question uses a greedy right-to-left digit scan.

Why is this asked in interviews?

Credit Karma, Amazon, and SAP ask this to test digit manipulation and greedy reasoning. The insight — that when a digit exceeds the next, you decrement it and set everything to the right to 9 — requires careful thinking about how digit changes propagate. The math and greedy interview pattern is directly demonstrated.

Algorithmic pattern used

Greedy right-to-left scan. Convert the number to a digit array. Scan from right to left: whenever a digit is greater than the next digit, decrement it by 1 and mark all positions to its right as '9'. After the scan, rebuild the number. The mark position tracks where 9s should begin.

Example explanation

N = 332.

• Compare digits right-to-left: 3 > 2? Yes (index 1 vs 2). Set digits[1] = 2, mark = 2.
• Compare digits[0] vs digits[1]: 3 > 2? Yes. Set digits[0] = 2, mark = 1.
• Set all digits from mark onward to 9: digits = [2, 9, 9]. Result = 299.

N = 1234: already monotone increasing → answer = 1234.

Common mistakes candidates make

• Processing left-to-right (misses cascading decrements).
• Not propagating 9s from the mark position to the end.
• Forgetting to handle the entire digit string, not just the first violation.
• Comparing digits as strings instead of integers.

Interview preparation tip

Digit greedy problems often require scanning from right to left to handle cascading effects. The pattern: find the rightmost violation, fix it (decrement), fill everything to the right with 9 (maximum value). This maximizes the number while maintaining the constraint. Practice similar problems like "remove k digits to get smallest number" — they use the same rightward 9-fill / leftward decrement structure with monotone stack variations.