Lexicographical Numbers

Medium
1599.

Lexicographical Numbers

Lexicographical Numbers is a medium coding problem on depth-first search and trie, asked in Amazon, Google and Bloomberg interviews.

Given an integer n, return every integer from 1 to n (inclusive) arranged in lexicographical order — the order a dictionary would list them if each number were written out as a string of digits.

So 10 comes before 2 (the string "10" starts with "1"), and 1 comes before 10 (a prefix sorts first).

Your algorithm should run in O(n) time and use O(1) extra space beyond the output.

Example 1

Input
n = 13
Output
[1,10,11,12,13,2,3,4,5,6,7,8,9]
Explanation
Every number that starts with the digit 1 comes before 2.

Example 2

Input
n = 2
Output
[1,2]

Example 3

Input
n = 1
Output
[1]

Constraints

  • 1 <= n <= 5 * 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number[]}
 */
var lexicalOrder = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Lexicographical Numbers — Solution in Python, Java & C++

Lexicographical Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Lexicographical Numbers is a medium coding problem on depth-first search and trie, asked in Amazon, Google and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trie
  • Asked at: Amazon, Google, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer n, return every integer from 1 to n (inclusive) arranged in lexicographical order — the order a dictionary would list them if each number were written out as a string of digits.

So 10 comes before 2 (the string "10" starts with "1"), and 1 comes before 10 (a prefix sorts first).

Your algorithm should run in O(n) time and use O(1) extra space beyond the output.

Example 1

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Explanation: Every number that starts with the digit 1 comes before 2.

Example 2

Input: n = 2
Output: [1,2]

Example 3

Input: n = 1
Output: [1]

Constraints

  • 1 <= n <= 5 * 10^4

Hints for Lexicographical Numbers

  1. Hint 1

    Picture the numbers as a tree: the children of x are 10x, 10x + 1, …, 10x + 9. Lexicographic order is a pre-order walk of that tree.

  2. Hint 2

    You don't need recursion or a stack — from the current number you can compute the next one directly.

  3. Hint 3

    Go down (x * 10) when that is still <= n. Otherwise step to the next sibling x + 1, but first climb up (x / 10) while x ends in 9 or x + 1 > n.

How to solve Lexicographical Numbers

Lexicographic order on decimal strings is exactly a pre-order traversal of the 10-ary tree whose root's children are 1…9 and where x has children 10x … 10x + 9. The successor of any node in that walk can be computed in amortised constant time, so the whole list is produced without sorting.

Approach

  1. Start with cur = 1 and repeat n times: append cur to the answer.
  2. If cur * 10 <= n, the next number is its first child cur * 10.
  3. Otherwise, while cur ends in 9 or cur + 1 > n, climb to the parent cur / 10 (integer division).
  4. Then move to the next sibling: cur += 1.

Why it works

In a pre-order walk the node after x is its first child if it has one; if not, it is the next sibling of the nearest ancestor (including x itself) that still has a next sibling inside 1…n. A node ending in 9 is a last child, and x + 1 > n means the sibling is out of range — in both cases we climb. Each climb undoes an earlier descent, so the total work is O(n).

Complexity

  • Time — O(n)
  • Space — O(1) besides the output

Pitfalls

  • Sorting the numbers as strings works but costs O(n log n) and allocates a string per number.
  • Climbing must also happen when cur + 1 > n, not only when cur ends in 9 — e.g. after 13 with n = 13 the next number is 2.
  • cur * 10 stays far below 2^31 because cur <= n <= 5 * 10^4.

Reference solution

Python

from typing import List

def lexicalOrder(n: int) -> List[int]:
    out = []
    cur = 1
    for _ in range(n):
        out.append(cur)
        if cur * 10 <= n:
            cur *= 10
        else:
            while cur % 10 == 9 or cur + 1 > n:
                cur //= 10
            cur += 1
    return out

Java

public static int[] lexicalOrder(int n) {
    int[] out = new int[n];
    int cur = 1;
    for (int i = 0; i < n; i++) {
        out[i] = cur;
        if (cur * 10 <= n) {
            cur *= 10;
        } else {
            while (cur % 10 == 9 || cur + 1 > n) cur /= 10;
            cur += 1;
        }
    }
    return out;
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Trie (Prefix Tree)