Eg. For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
The below solution works, quite well actually. I found it after struggling a bit, and I can't understand how it's actually working. It seems like pure magic. When we make the recursive call, how in the world is the start argument still 10 after the second time recursing
public static ArrayList<Integer> lexicalOrder(int n) {
ArrayList<Integer> result = new ArrayList<>();
dfs(1, 9, n, result);
return result;
}
private static void dfs(int start, int end, int n, ArrayList<Integer> result){
for (int i = start; i <= end && i <= n; i++){
result.add(i);
//Just printing out the end and start to try to understand
System.out.println("Start : " + start + " End : " + end);
//If i is 10, how does 10 * 10 end up as 10 again for several iterations???
dfs(i * 10, i * 10 + 9, n, result);
}
}
I don't believe in magic, so can someone please explain how this is working? First iteration start is 1 and end is 9 as expected. Then start is 10 and 19 as I expected on the second iteration. Then, I expect start to be 100, and end to be 109 after we make our next recursive call; however, they are as they were on the previous recursion: 10 and 19.
It's very simple. You have both recursion and a loop. Thus the first call to dfs(1,9,13) actually does this:
add 1 to result and call dfs (10,19,13),
add 2 to result and call dfs (20,29,13)
...
add 9 to result and call dfs (90,99,13).
Only the call to dfs (10,19,13) actually does anything because in all other cases the first two parameters are greater than the 3rd.
The call to dfs (10,19,13) does this:
add 10 to result and call dfs (100, 109, 13)
add 11 to result and call dfs (110, 119, 13)
add 12 to result and call dfs (120, 129, 13)
add 13 to result and call dfs (130, 139, 13)
it then terminates because 14 is greater than 13.
The behaviour you are seeing, of start and end going back to 10 and 13, are simply a result of this second set of recursive calls terminating and returning to the enclosing loop.