Lexicographical Numbers

medium dfs trie

Problem

Given an integer n, return numbers 1..n in lexicographical order.

Inputn = 13

Output[1,10,11,12,13,2,3,4,5,6,7,8,9]

Walk 1→10→11→12→13→(back to 2)→3→…→9.

def lex_order(n):
    out = []
    cur = 1
    for _ in range(n):
        out.append(cur)
        if cur * 10 <= n:
            cur *= 10
        else:
            if cur >= n: cur //= 10
            cur += 1
            while cur % 10 == 0: cur //= 10
    return out

function lexicalOrder(n) {
  const out = [];
  let cur = 1;
  for (let i = 0; i < n; i++) {
    out.push(cur);
    if (cur * 10 <= n) cur *= 10;
    else {
      if (cur >= n) cur = Math.floor(cur / 10);
      cur++;
      while (cur % 10 === 0) cur = Math.floor(cur / 10);
    }
  }
  return out;
}

class Solution {
    public List lexicalOrder(int n) {
        List out = new ArrayList<>();
        int cur = 1;
        for (int i = 0; i < n; i++) {
            out.add(cur);
            if ((long) cur * 10 <= n) cur *= 10;
            else {
                if (cur >= n) cur /= 10;
                cur++;
                while (cur % 10 == 0) cur /= 10;
            }
        }
        return out;
    }
}

vector lexicalOrder(int n) {
    vector out;
    int cur = 1;
    for (int i = 0; i < n; i++) {
        out.push_back(cur);
        if ((long long) cur * 10 <= n) cur *= 10;
        else {
            if (cur >= n) cur /= 10;
            cur++;
            while (cur % 10 == 0) cur /= 10;
        }
    }
    return out;
}

Explanation

Lexicographic (dictionary) order of numbers is the same as walking a 10-ary trie of their digits: 1, then 10, 11, …, then 2, and so on. This solution walks that order directly with a single variable cur, never building a tree.

From any number, the smallest next number in dictionary order is one digit deeper, so we try to multiply by 10. If cur * 10 <= n we descend into that child.

If we cannot go deeper, we move to the next sibling by adding 1. But if adding 1 would overshoot n or roll a digit over (giving a trailing zero), we first climb back up by dividing by 10 until cur ends in a non-zero digit. That climb-then-step is the rollback the loop performs.

Example: n = 13. 1 → 10 → 11 → 12 → 13; now 14 > 13 so step back to 1, +1 gives 2; then 3, 4, …, 9. Output: [1,10,11,12,13,2,3,4,5,6,7,8,9].

We emit exactly n numbers and only adjust cur a constant amount each time, so it runs in O(n) with O(1) extra space.

Time: O(n) Space: O(1)