package interview;

import java.util.Arrays;

import java.util.Scanner;

public class LargestNumberBeforN {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

String a = sc.next();

for (int i = a.length() - 1; i > 0; i--) {

if (a.charAt(i) = 0; i--) {

b = b + String.valueOf(a[i]);

}

return b;

}

}

I gave the obvious solution of generating all permutations of the number n and ordering them, find the one that occurs before n.

Then I figured out that if I sort the digits from a certain point onwards into increasing order, it can help me build up to the solution. I proposed my algorithm and we began doing some really sort of pseudofunctional java code that solved the problem. After the end of that, I analyzed my solution and found it to run in O(n^2) time utilizing a bucket sort for the sorting operation. This was a big improvement from O(n!) but still not optimum. He explained the optimum solution found a pivot at which point it sorted the digits, running in O(n).