Monotone Increasing Digits

MediumGreedygreedy

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

An integer has **monotone increasing digits** when each decimal digit is less than or equal to the digit to its right (for example 1229 or 7). Given a non-negative integer n, return the **largest** integer that is less than or equal to n and has monotone increasing digits. Aim for O(d) time where d is the number of digits of n.

Examples

Input: n = 332
Output: 299
Anything from 300 to 332 has a 3 followed by a smaller digit. 299 is the largest valid value.
Input: n = 1234
Output: 1234
The digits already never decrease.
Input: n = 10
Output: 9
10 has digits 1 then 0, so the answer drops to 9.

Constraints

  • 0 <= n <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy problems