In this guide, you will get 738. Monotone Increasing Digits LeetCode Solution with the best time and space complexity. The solution to Monotone Increasing Digits problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 <= 109
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
738. Monotone Increasing Digits LeetCode Solution in C++
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);
}
}; /* code provided by PROGIEZ */
738. Monotone Increasing Digits LeetCode Solution in Java
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));
}
} // code provided by PROGIEZ
738. Monotone Increasing Digits LeetCode Solution in Python
