Approach #1: Greedy [Accepted]
Let's construct the answer digit by digit.
If the current answer is say,
123, and the next digit is
5, then the answer must be at least
123555...5, since the digits in the answer must be monotonically increasing. If this is larger than
N, then it's impossible.
For each digit of
N, let's build the next digit of our answer
ans. We'll find the smallest possible digit
d such that
ans + (d repeating) > N when comparing by string; that means
d-1 must have satisfied
ans + (d-1 repeating) <= N, and so we'll add
d-1 to our answer. If we don't find such a digit, we can add a
Time Complexity: , where is the number of digits in . We do work building and comparing each candidate, and we do this times.
Space Complexity: , the size of the answer and the temporary string we are comparing.
Approach #2: Truncate After Cliff [Accepted]
One initial thought that comes to mind is we can always have a candidate answer of
d999...9 (a digit
0 <= d <= 9 followed by some number of nines.) For example if
N = 432543654, we could always have an answer of at least
We can do better. For example, when the number is
123454321, we could have a candidate of
123449999. It seems like a decent strategy is to take a monotone increasing prefix of
N, then decrease the number before the "cliff" (the index where adjacent digits decrease for the first time) if it exists, and replace the rest of the characters with
When does that strategy fail? If
N = 333222, then our strategy would give us the candidate answer of
332999 - but this isn't monotone increasing. However, since we are looking at all indexes before the original first occurrence of a cliff, the only place where a cliff could exist, is next to where we just decremented a digit.
Thus, we can repair our strategy, by successfully morphing our answer
332999 -> 329999 -> 299999 with a linear scan.
We'll find the first cliff
S[i-1] > S[i]. Then, while the cliff exists, we'll decrement the appropriate digit and move
i back. Finally, we'll make the rest of the digits
9s and return our work.
We can prove our algorithm is correct because every time we encounter a cliff, the digit we decrement has to decrease by at least 1. Then, the largest possible selection for the rest of the digits is all nines, which is always going to be monotone increasing with respect to the other digits occurring earlier in the number.
Time Complexity: , where is the number of digits in . Each step in the algorithm is a linear scan of the digits.
Space Complexity: , the size of the answer.
Analysis written by: @awice.