Monotone Increasing Digits

MEDIUM

Description

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

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

Example 1:

Input: n = 10
Output: 9

Example 2:

Input: n = 1234
Output: 1234

Example 3:

Input: n = 332
Output: 299

Constraints:

0 <= n <= 10⁹

Approaches

Checkout 2 different approaches to solve Monotone Increasing Digits. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves checking every integer, starting from n and going downwards, until we find one that has monotone increasing digits. For each integer, we verify the property by comparing its adjacent digits.

Algorithm

Start a loop with a variable i initialized to n.
In each iteration, check if the number i has monotone increasing digits.
To perform the check, create a helper function isMonotone(num):
- Convert num to its string representation, s.
- Iterate through the string s from the first character to the second-to-last character.
- If at any point s.charAt(j) > s.charAt(j+1), the number is not monotone, so return false.
- If the loop completes without finding such a violation, return true.
If isMonotone(i) returns true, then i is the largest monotone increasing number less than or equal to n. Return i.
If not, decrement i and continue the loop.
The loop will eventually terminate because 0 is a monotone increasing number.

The most straightforward way to solve this problem is to use a brute-force search. We start with the given number n and check if it satisfies the monotone increasing digit property. If it does, we have found our answer since we are looking for the largest number less than or equal to n. If it doesn't, we decrement the number by one and repeat the process. We continue this until we find a valid number. Since 0 is a valid monotone increasing number, this process is guaranteed to terminate.

A helper function can be used to check if a number is monotone increasing. This function would convert the number to a string or an array of digits and then iterate through them, ensuring that each digit is less than or equal to the next one.

Here is a code snippet for this approach:

class Solution {
    public int monotoneIncreasingDigits(int n) {
        for (int i = n; i >= 0; i--) {
            if (isMonotone(i)) {
                return i;
            }
        }
        return 0; // Should not be reached for n >= 0
    }

    private boolean isMonotone(int num) {
        String s = String.valueOf(num);
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) > s.charAt(i + 1)) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(N * D), where N is the input number and D is the number of digits in N (D = log₁₀N). In the worst-case scenario (e.g., n = 100000000), we might have to check many numbers. This complexity is too high for the given constraint `n <= 10^9`.Space Complexity: O(D) or O(log n), where D is the number of digits in n. This space is used to store the string representation of the number being checked.

Pros and Cons

Pros:

Simple to understand and implement.
Correct for all valid inputs, given enough time.

Cons:

Extremely inefficient for large values of n.
Will likely cause a 'Time Limit Exceeded' (TLE) error on most online judges for the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Monotone Increasing Digits. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Monotone Increasing Digits

Patterns:

MathGreedy

Companies:

SAP |