MonotoneIncreasingDigits.java

package string;

/**
 * Created by gouthamvidyapradhan on 01/05/2018.
 * Given a non-negative integer N, find the largest number that is less than or equal to N with monotone
 * increasing digits.

 (Recall that an integer has monotone increasing digits if and only if each pair of
 adjacent digits x and y satisfy x <= y.)

 Example 1:
 Input: N = 10
 Output: 9
 Example 2:
 Input: N = 1234
 Output: 1234
 Example 3:
 Input: N = 332
 Output: 299
 Note: N is an integer in the range [0, 10^9].

 Solution O(N): Convert to string for easier manipulation.
 Start from N.length - 1 and iterate through until index 0.Mark the index where the violation occurs.
 Decrement the value of the latest index where the violation occurs and append '9' to
 rest of the trailing digits. Convert the string to integer before returning.
 */
public class MonotoneIncreasingDigits {
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception{
        System.out.println(new MonotoneIncreasingDigits().monotoneIncreasingDigits(100001));
    }

    public int monotoneIncreasingDigits(int N) {
        String s = String.valueOf(N);
        if(s.length() == 1) return N;
        int p = -1;
        int prev = N % 10;
        for(int i = s.length() - 2; i >= 0; i--){
            int curr = Integer.parseInt(String.valueOf(s.charAt(i)));
            if(curr > prev){
                p = i;
                prev = curr - 1;
            } else {
                prev = curr;
            }
        }
        if(p == -1) return N;
        StringBuilder result = new StringBuilder();
        for(int i = 0; i < s.length(); i ++){
            if(i == p){
                int pV = Integer.parseInt(String.valueOf(s.charAt(i)));
                result.append(pV - 1);
                break;
            } result.append(String.valueOf(s.charAt(i)));
        }
        for(int i = p + 1; i < s.length(); i ++){
            result.append("9");
        }
        return Integer.parseInt(result.toString());
    }

}