Monotone Increasing Digits Solution in C++

Navigate to Other Solutions

Problem Description

Ah, the Monotone Increasing Digits problem! It’s like trying to keep your life in order while your digits are throwing a wild party. The task is to find the largest number less than or equal to a given number n such that all of its digits are in non-decreasing order. Imagine you’re at a buffet, and you can only take food in increasing amounts. You can’t take a smaller plate after a bigger one, right?

For example, if you have n = 332, the largest number you can form with non-decreasing digits is 299. Why? Because 3 is a party animal and decided to drop down to 2 to keep things in line.

Code Solution


class Solution {
 public:
  int monotoneIncreasingDigits(int n) {
    string s = to_string(n);
    const 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 stoi(s);
  }
};

Approach Explanation

The approach here is as straightforward as a Sunday morning. We convert the number into a string to easily manipulate its digits. We then traverse the string from the end to the beginning, looking for the first instance where a digit is less than the one before it. When we find it, 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 n while maintaining the monotonic property.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(d), where d is the number of digits in `n`.
Space Complexity	O(d) as well, since we are storing the digits in a string.

Real-World Example

Imagine you’re at a concert, and the crowd is getting rowdy. You can only let people in if they’re in a line that’s not decreasing. If someone tries to cut in front of a taller person, you have to send them back to the end of the line. This is exactly what our algorithm does with the digits of n—it ensures that everyone is in line, and if they’re not, it makes the necessary adjustments.