Lexicographical Numbers

LeetCode Q 386 - Lexicographical Numbers

Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

Solution

Solution 1: Sort O(nlogn)

Code:

public List<Integer> lexicalOrder(int n) {
  List<Integer> list = new ArrayList<>();
  
  for (int i = 1; i <= n; i++) list.add(i);

  Collections.sort(list, (a, b) -> {
    return String.valueOf(a).compareTo(String.valueOf(b));
  });

  return list;
}

Solution 2: DFS O(n)

Code:

List<Integer> list;
public List<Integer> lexicalOrder(int n) {
  list = new ArrayList<>();
  
  for (int i = 1; i <= 9; i++) {
    if (i > n) break;
    dfs(n, i);
  }

  return res;
}

private void dfs(int n, int currNum) {
  res.add(current);
  for (int i = 0; i <= 9; i++) {
    if (currNum * 10 + i > n) break;
    dfs(n, currNum * 10 + i);
  }
}