Simple Python solution w/ Explanation


  • 13

    The idea is to go from the LSB to MSB and find the last digit, where an inversion happens.
    There are 2 cases to consider:

    case 1:
    In 14267 , we see that inversion happens at 4. In this case, then answer is obtained by reducing 4 to 3, and changing all the following digits to 9.
    => 13999

    case 2:
    1444267, here eventhough the last inversion happens at the last 4 in 1444, if we reduce it to 3, then that itself breaks the rule. So once we find the last digit where inversion happens, if that digit is repeated, then we have to find the last position of that digit. After that it is same as case1, where we reduce it by 1 and set the remaining digits to 9.
    => 1399999

    The steps are:

    1. Convert n into num array in reverse order
    2. Find the leftmost position that is inverted and if the inverted character repeats itself, find the leftmost repeated digit.
    3. Fill the digits after inversion as 9
    4. Reduce the digit that caused the inversion by -1
    5. Reverse back the num array and convert to int
    def monotoneIncreasingDigits(self, N):
            if N < 10: return N
            n, inv_index = N, -1
            num = [int(d) for d in str(n)[::-1]] 
    
            for i in range(1, len(num)): 
                if num[i] > num[i - 1] or (inv_index != -1 and num[inv_index] == num[i]):
                    inv_index = i
    
            if inv_index == -1: return N
    
            for i in range(inv_index): num[i] = 9
            num[inv_index] -= 1
            
            return int(''.join([ str(i) for i in num[::-1]])) 
    

  • 1

    Nice logic! :)


  • 8

    Great solution! A Java version:

    class Solution {
        public int monotoneIncreasingDigits(int N) {
            final String s = String.valueOf(N);
            int n = s.length(), idx = -1;
            for (int i = n - 2; i >= 0; i--) {
                if ((s.charAt(i) > s.charAt(i + 1)) || ((idx != -1) && (s.charAt(idx) == s.charAt(i)))) {
                    idx = i;
                }
            }
            return (idx == -1) ? N : N - Integer.parseInt(s.substring(idx + 1, n)) - 1;
        }
    }
    

  • 0
    M

    @jianchao.li.fighter said in Simple Python solution w/ Explanation:

    2; i >= 0; i--) {
    if ((s.charAt(i) > s.charAt(i + 1)

    Hi! Thanks for your java version! Can you explain what's the idx for? Thanks!


  • 1
    W

    Thanks, great approach. Java Implementation of the Idea.

    public int monotoneIncreasingDigits(int N) {
        char[] num = String.valueOf (N).toCharArray();
        for (int idx = 0, start = 0; idx < num.length - 1; idx ++) {
            if (num [idx] > num [idx + 1]) {
                num [start] --;
                for (int jdx = start + 1; jdx < num.length; jdx ++) num [jdx] = '9';
            } else if (num [idx] < num [idx + 1]) start = idx + 1;
        }
        return Integer.valueOf (String.valueOf (num));
    }
    

  • 1
    L

    @Warrior nice solution!


  • 1
    W

    Same idea but I did not reverse the number.

    class Solution(object):
        def monotoneIncreasingDigits(self, N):
            """
            :type N: int
            :rtype: int
            """
            if N<10: return N
            A=list(str(N))
            i,n=0,len(A)
    
            # identify the position when decrease occurs
            while i<n-1 and A[i]<=A[i+1]: i+=1
    
            # if i==n-1, that means no decrease
            if i==n-1: return N
    
            # identify the position for equal situation
            while i>0 and A[i]==A[i-1]: i-=1
    
            # subtract 1 for i and fill the remaining 9
            A[i]=str(int(A[i])-1)
            A[i+1:]=['9']*(n-i-1)
    
            return int(''.join(A))

  • 1

    Another straightforward solution based on your idea.

    public int monotoneIncreasingDigits(int N) {
        char[] number = String.valueOf(N).toCharArray();
        for(int i = 1; i<number.length;i++){
            //if it is monotone increasing, continue
            //else we hit the decreasing breakpoint below
            if(number[i]<number[i-1]) {
                int breakpoint = i-1;
                while(--i>=0) {
                    if((i-1)>=0&&number[i-1]==number[i]) number[i]='9';
                    else{
                        number[i]=(char)(number[i]-1);
                        break;
                    }
                }
                while(++breakpoint<number.length) number[breakpoint]='9';
                break;
            }
        }
        return Integer.valueOf(String.valueOf(number));
    }

  • 0
    T

    Java version:

    class Solution {
        public int monotoneIncreasingDigits(int N) {
              String str = new StringBuilder(N+"").toString();
              int[] nums = new int[str.length()];
              for(int i=0;i<str.length();i++){
                  nums[i] = str.charAt(i)-'0';
              }
            
              int find_index = -1;
              for(int i=0;i<nums.length-1;i++){
                  if(nums[i+1]<nums[i]){
                      find_index = i+1;
                      break;
                  }
              }
            
              if(find_index == -1){
                  return N;
              }
              find_index--;
              while(find_index>=0){
                  nums[find_index]--;
                  if(find_index==0 || (find_index>0 && nums[find_index]>=nums[find_index-1])){
                      break;
                  }
                  find_index--;
              }  
              
              
              for(int i=find_index+1;i<nums.length;i++){
                  nums[i] = 9;
              }
              int p = 0;
              while(p<nums.length && nums[p]==0){
                  p++;
              }
            
              int res = 0;
              System.out.println(Arrays.toString(nums));
              while(p<nums.length){
                  res = res*10+nums[p];
                  p++;
              }
            
              return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.