Problem statement

https://leetcode.com/problems/monotone-increasing-digits/

Solution

One way to solve it is greedy approach, where we try to built digit by digit in O(k^2) time.

There is smarter solution with O(k) time and space complexity: we need to find the first place, when digit is decreasing, for example in number 1123334429, it will be 11233344. Then for the last group of repeating digits we need to decrease first one by one and put rest of digits as 9, so the answer will be 1123333999. Also we need to check case, when there is not place when digits decrease, then we return original number.

Complexity

Time and space complexity is O(k), where k number of digits in N.

Code

class Solution:
    def monotoneIncreasingDigits(self, N):
        prefix, k = ["0"], len(str(N))
        for digit in str(N):
            if digit >= prefix[-1]:
                prefix += [digit]
            else:
                break
        
        if len(prefix) == k + 1: return N
        
        q = prefix.index(prefix[-1])
        return int("".join(prefix[1:q]) + str(int(prefix[q])-1) + "9"*(k-q))