Leetcode 738. Monotone Increasing Digits
Problem explanation
The problem requires finding the largest number with monotone increasing digits that is less than or equal to a given non-negative integer N
. A number has monotone increasing digits if each digit is less than or equal to the digit right after it.
For example, if the given number is 332
, it contains a pair of adjacent digits (3
, 2
) that does not satisfy the condition of monotone increasing digits (3
> 2
). In such a case, we would need to convert this number into the largest number that satisfies the condition of monotone increasing digits and is less than 332
, which is 299
.
On the other hand, if the given number is 1234
, it already satisfies the condition of monotone increasing digits (as 1
<= 2
, 2
<= 3
, and 3
<= 4
), and thus, the output of the function would be 1234
(the same input number).
Solution explanation
The algorithm follows this steps:
- Convert the number to a string for easy manipulation of digits.
- Iterate over the digits from right to left.
- If a digit is less than the one to its right, subtract one from the current digit and change all the digits to its right to
9
. This ensures that the new number is less than the original number but also the largest number with monotone increasing digits. - Convert the string back to an integer before returning the result.
Python solution
1 2python 3class Solution: 4 def monotoneIncreasingDigits(self, N: int) -> int: 5 # Convert the number to a string for easy manipulation of digits 6 number_str = list(str(N)) 7 i = len(number_str) - 1 8 9 while i > 0: 10 # If current digit is smaller than previous digit 11 if number_str[i] < number_str[i-1]: 12 # Subtract 1 from previous digit 13 number_str[i-1] = str(int(number_str[i-1]) - 1) 14 # Set current digit and all following digits to '9' 15 for j in range(i, len(number_str)): 16 number_str[j] = '9' 17 i -= 1 18 19 return int(''.join(number_str))
Java solution
1
2java
3class Solution {
4 public int monotoneIncreasingDigits(int N) {
5 char[] digits = Integer.toString(N).toCharArray();
6 int i, j;
7 for (i = 1; i < digits.length && digits[i-1] <= digits[i]; i++);
8 if(i < digits.length) {
9 for (j = i; j > 0 && digits[j-1] > digits[j]; j--)
10 digits[j-1]--;
11 for (j++; j < digits.length; j++)
12 digits[j] = '9';
13 }
14 return Integer.parseInt(new String(digits));
15 }
16}
JavaScript solution
1
2javascript
3var monotoneIncreasingDigits = function(N) {
4 const chars = N.toString().split('');
5 let i = 1;
6 while (i < chars.length && chars[i-1] <= chars[i]) i++;
7 while (0 < i && i < chars.length && chars[i-1] > chars[i]) chars[--i]--;
8 for (i++; i < chars.length; i++) chars[i] = '9';
9
10 return Number(chars.join(''));
11};
C++ solution
1 2cpp 3class Solution { 4public: 5 int monotoneIncreasingDigits(int N) { 6 string num = to_string(N); 7 int mark = num.size(); 8 for(int i = num.size()-1; i > 0; i--){ 9 if(num[i] < num[i-1]){ 10 mark = i; 11 num[i-1]--; 12 } 13 } 14 for(int i = mark; i < num.size(); i++) 15 num[i] = '9'; 16 return stoi(num); 17 } 18};
C# solution
1
2csharp
3public class Solution {
4 public int MonotoneIncreasingDigits(int N) {
5 string strN = N.ToString();
6 char[] arr = strN.ToCharArray();
7
8 int i = 1;
9 while (i < arr.Length && arr[i - 1] <= arr[i]) i++;
10
11 if (i < arr.Length) {
12 while (i > 0 && arr[i - 1] > arr[i]) arr[--i]--;
13 for (i++; i < arr.Length; i++) arr[i] = '9';
14 }
15
16 return Int32.Parse(new string(arr));
17 }
18}
Swift solution
1 2swift 3class Solution { 4 func monotoneIncreasingDigits(_ N: Int) -> Int { 5 var chars = Array(String(N)) 6 var i = 1 7 while i < chars.count && chars[i-1] <= chars[i] { 8 i += 1 9 } 10 if i < chars.count { 11 while i > 0 && chars[i-1] > chars[i] { 12 chars[i-1] = Character(String(Int(String(chars[i-1]))! - 1)) 13 i -= 1 14 } 15 for j in i..<chars.count { 16 chars[j] = "9" 17 } 18 } 19 return Int(String(chars))! 20 } 21}
This Swift solution follows the same steps as the previous ones. We start by converting the given integer N
to a String
and then to an Array
of Character
s to be able to manipulate its individual digits. Then, we iterate through the characters, compare each one to the previous one, and adjust the digits accordingly to ensure we form the largest possible number with monotonically increasing digits.
Kotlin solution
1 2kotlin 3class Solution { 4 fun monotoneIncreasingDigits(N: Int): Int { 5 val chars = N.toString().toCharArray() 6 var i = 1 7 while (i < chars.size && chars[i - 1] <= chars[i]) i++ 8 while (i > 0 && i < chars.size && chars[i - 1] > chars[i]) { 9 chars[--i]-- 10 } 11 for (index in i + 1 until chars.size) { 12 chars[index] = '9' 13 } 14 return String(chars).toInt() 15 } 16}
In this Kotlin solution, we convert the given integer N
to a String
and then to a CharArray
so that we can manipulate its individual digits. We then use two while
loops to adjust the digits to form the largest number with monotonically increasing digits.
We hope this comprehensive list of solutions helps you understand how to solve the given problem using different programming languages efficiently. Remember that understanding the algorithm is more important than the programming language used to implement it. If you understand the solution well, you can implement it in any programming language of your choice.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.