Monotone Increasing Digits Solution in Java

Navigate to Other Solutions

Problem Description

So, you think you can just throw any number at the wall and expect it to stick? Well, think again! The Monotone Increasing Digits problem is here to remind you that numbers have feelings too. The task is to take a number n and transform it into the largest number that is less than or equal to n and has digits that are in non-decreasing order.

Imagine you’re at a party, and you want to wear the fanciest outfit. But wait! You realize your favorite shirt has a button that’s about to pop. You can’t just wear it like that; you need to make some adjustments. Similarly, we need to adjust our number to ensure it looks good in monotone increasing order.

Code Solution

class Solution {
  public int monotoneIncreasingDigits(int n) {
    char[] s = String.valueOf(n).toCharArray();
    final int n = s.length;
    int k = n; // s[k..n) -> '9'

    for (int i = n - 1; i > 0; --i)
      if (s[i] < s[i - 1]) {
        --s[i - 1];
        k = i;
      }

    for (int i = k; i < n; ++i)
      s[i] = '9';

    return Integer.parseInt(new String(s));
  }
}

Approach

The approach here is as straightforward as a Sunday morning. We convert the number into a character array to manipulate its digits. Starting from the end of the array, we check if the current digit is less than the previous one. If it is, we decrement the previous digit and set all subsequent digits to '9'. This ensures that we get the largest possible number that is still less than or equal to the original number while maintaining the monotonic property.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(d), where d is the number of digits in the number.
Space Complexity	O(d) as well, since we are using a character array to store the digits.

Real-World Example

Let’s say you’re trying to buy a car, and you have a budget of $54321. However, the car you want is $54322. You can’t afford it, but you can negotiate to get the best deal possible. In this case, the best deal would be to get a car for $53999, which is the largest number less than $54322 that has digits in non-decreasing order.