Monotone Increasing Digits

Medium
358.

Monotone Increasing Digits

Monotone Increasing Digits is a medium coding problem on math and greedy, asked in Amazon and Google interviews.

An integer has monotone increasing digits if each digit is at least as large as the one before it.

Given an integer n, return the largest number less than or equal to n with monotone increasing digits.

Example 1

Input
n = 10
Output
9

Example 2

Input
n = 1234
Output
1234
Explanation
It already qualifies.

Example 3

Input
n = 332
Output
299

Constraints

  • 0 <= n <= 100000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var monotoneIncreasingDigits = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Monotone Increasing Digits — Solution in Python, Java & C++

Monotone Increasing Digits solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Monotone Increasing Digits is a medium coding problem on math and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An integer has monotone increasing digits if each digit is at least as large as the one before it.

Given an integer n, return the largest number less than or equal to n with monotone increasing digits.

Example 1

Input: n = 10
Output: 9

Example 2

Input: n = 1234
Output: 1234
Explanation: It already qualifies.

Example 3

Input: n = 332
Output: 299

Constraints

  • 0 <= n <= 100000000

Hints for Monotone Increasing Digits

  1. Hint 1

    Walk the digits from the right. Wherever a digit is smaller than the one before it, that earlier digit must come down by one.

  2. Hint 2

    Everything after the last such break can then be raised to 9.

  3. Hint 3

    Do the scan right to left in one pass so cascading breaks (like 332 → 329 → 299) resolve correctly.

How to solve Monotone Increasing Digits

Scan right to left; wherever a digit is smaller than its predecessor, decrement the predecessor and mark the position; then set everything after the last mark to 9.

Approach

  1. For i from the end down to 1, if d[i-1] > d[i]: d[i-1] -= 1, mark = i.
  2. Set d[j] = 9 for j >= mark.
  3. Parse the digits.

Why it works

The largest monotone number ≤ n shares the longest possible prefix with n; at the first break the prefix digit must drop by one, and the suffix is then free to be all 9s. Scanning right to left resolves cascades (332 → 299).

Complexity

  • Time — O(digits)
  • Space — O(digits)

Pitfalls

  • A left-to-right scan misses cascades where the decrement creates a new break.

Reference solution

Python

def monotoneIncreasingDigits(n: int) -> int:
    digits = [int(c) for c in str(n)]
    mark = len(digits)
    for i in range(len(digits) - 1, 0, -1):
        if digits[i - 1] > digits[i]:
            digits[i - 1] -= 1
            mark = i
    for i in range(mark, len(digits)):
        digits[i] = 9
    return int("".join(str(d) for d in digits))

Java

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

C++

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

JavaScript

var monotoneIncreasingDigits = function(n) {
    const digits = String(n).split("").map(Number);
    let mark = digits.length;
    for (let i = digits.length - 1; i > 0; i--) {
        if (digits[i - 1] > digits[i]) {
            digits[i - 1]--;
            mark = i;
        }
    }
    for (let i = mark; i < digits.length; i++) digits[i] = 9;
    return parseInt(digits.join(""), 10);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Greedy Algorithms