Problem statement

https://binarysearch.com/problems/Non-Decreasing-Digits/

Solution

Equal to Leetcode 0738 Monotone Increasing Digits.

Complexity

It is O(k) for time and space.

Code

class Solution:
    def solve(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))