Monotone Increasing Digits

'''
Intuition:
A monotone increasing number never decreases from left to right.
If a digit is bigger than the next one, the number becomes invalid.
To fix this while staying ≤ n, we reduce the left digit by 1.
Then we make all digits to the right as large as possible by setting them to 9.
This gives the largest valid number not greater than n.

for eg. input=[3,3,2] so it's biggest monotone increasing would be 299 so observation you are taking the first place whose right element is not smaller than it and reduce it by 1 and all elements after that converted to 9 so do the same.
'''
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        digits = list(map(int, str(n)))
        mark = len(digits)
        print(digits, mark)

        # Traverse from right to left
        for i in range(len(digits) - 1, 0, -1): #we are doing from left to right bcz left to right will not consider the prev elements
            if digits[i - 1] > digits[i]:
                digits[i - 1] -= 1 #we are only reducing this element by 1 so that mark and onwards can be 9 and that would be fine.
                mark = i

        # Set all digits after mark to 9
        for i in range(mark, len(digits)):
            digits[i] = 9

        return int("".join(map(str, digits)))