@@ -0,0 +1,1143 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A * Given an integer n, return 1 - n in lexicographical order.%0A * %3Cp%3E%0A * For example, given 13, return: %5B1,10,11,12,13,2,3,4,5,6,7,8,9%5D.%0A * %3Cp%3E%0A * Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.%0A */%0Apublic class LexicographicalNumbers %7B%0A%0A    /**%0A     * DFS.%0A     * Search for the next possible number to add to result.%0A     *         1%0A     *     /       %5C%0A     *   10 ...    19%0A     *   /       /    %5C%0A     * 100 ...  190...199%0A     */%0A    public List%3CInteger%3E lexicalOrder(int n) %7B%0A        List%3CInteger%3E res = new ArrayList%3C%3E(n);%0A        for (int i = 1; i %3C 10; i++) %7B%0A            dfs(i, n, res);%0A        %7D%0A        return res;%0A    %7D%0A%0A    private void dfs(int curr, int n, List%3CInteger%3E res) %7B%0A        if (curr %3E n) %7B%0A            return;%0A        %7D%0A        res.add(curr);%0A        for (int i = 0; i %3C 10; i++) %7B%0A            int next = 10 * curr + i;%0A            if (next %3E n) %7B // Early prune%0A                return;%0A            %7D%0A            dfs(next, n, res);%0A        %7D%0A    %7D%0A%0A%7D%0A

add Lexicographical Numbers