Be the first user to complete this post

  • 1
 Add to List
Medium

372. Monotone Increasing Digits - Leetcode

Objective: Given a number N, find the largest number which is less than equal to N and has monotone increasing digits.

Monotone Increasing Digits - If all the pairs (x, y) of adjacent digits satisfy the property, x<=y. In other words if all digits are in ascending order (can have duplicates) then digits are called monotone increasing digits.

Example:

N = 324
Output: 299

N = 4321
Output: 3999

N = 12345
Output: 12345

Approach:

  1. Iterate the number from right to left (in reverse order).
  2. Find the last pair of adjacent digits (x, y) where x > y and store the index of x.
  3. In original number, put x-1 at the stored index and put 9 all the indexes at the right of the array.
  4. See the example below for more understanding.

 

N = 7384
pair 8, 4  8 > 4, stored index= 2
pair 3, 8  3 < 8, no change, stored index = 2
pair 7, 3  7 > 3, stored index = 0
Output  = 7 – 1 at the index 0 and put 9 at all the places at right => 6999
___________________________________________________________

N = 391
pair 9, 1  9 > 1, stored index = 1
pair 3, 9  3 < 9, no change in stored index
Output: 9 – 1 at the index 1 and put 9 at all the places at right => 389

 

 

Output:

N = 7384 monotone increasing: 6999
N = 1234 monotone increasing: 1234
N = 1111 monotone increasing: 1111
N = 4321 monotone increasing: 3999

Reference: here

Related Problems: