386. Lexicographical Numbers Solution

The problem

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space.

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 5 * 10⁴

Approach overview

Problem Overview: Given an integer n, return the numbers from 1 to n sorted in lexicographical (dictionary) order. The challenge is generating this order without converting all numbers to strings and sorting them, which would add unnecessary overhead.

Approach 1: DFS Prefix Traversal (O(n) time, O(h) space)

This problem maps naturally to a Trie-like prefix tree. Each number is treated as a prefix, and its children are formed by appending digits 0-9. Starting from prefixes 1 through 9, perform a depth-first traversal and keep expanding by multiplying the current number by 10 and adding digits. If the generated value exceeds n, stop exploring that branch. This produces numbers exactly in lexicographical order because DFS always explores the smallest prefix first.

The recursion depth corresponds to the number of digits in n, making the auxiliary space O(h) where h ≈ log10(n). This method is conceptually simple and mirrors how a Trie organizes numbers by prefixes. It’s also a clean application of Depth-First Search.

Approach 2: Iterative Lexicographical Traversal (O(n) time, O(1) space)

The iterative solution simulates the same prefix traversal without recursion. Start with current = 1. At each step, append the current number to the result. If current * 10 ≤ n, move to the smallest child (go deeper in the prefix tree). Otherwise, move to the next sibling by incrementing current. If the increment causes a trailing zero boundary or exceeds n, repeatedly divide by 10 until a valid next prefix is found.

This logic mimics walking through an implicit trie in lexicographical order. Instead of storing the tree, you navigate it using arithmetic operations like *10, +1, and /10. Every number from 1 to n is visited exactly once, giving O(n) time complexity while keeping extra space constant.

Recommended for interviews: Interviewers typically expect the iterative prefix traversal. It demonstrates understanding of lexicographical ordering and avoids recursion overhead, achieving O(n) time and O(1) extra space. The DFS approach is still valuable because it clearly shows the underlying trie structure and confirms your understanding of the traversal pattern.

Approach 1: DFS Approach

The idea is to perform a depth-first search (DFS) to generate numbers in lexicographical order. Starting from the number 1, we explore all numbers that can be formed by appending digits from 0 to 9 as long as the generated number is less than or equal to n. If we reach a number greater than n, backtrack and explore the next number at the same level and repeat the process.

Python

def dfs(current, n, result):
    if current > n:
        return
    result.append(current)
    for i in range(10):
        if current * 10 + i > n:
            return
        dfs(current * 10 + i, n, result)

def lexicalOrder(n):
    result = []
    for i in range(1, 10):
        dfs(i, n, result)
    return result

n = 13
print(lexicalOrder(n))

Java

import java.util.ArrayList;
import java.util.List;

public class Lexical
OrderDFS {
    private void dfs(int current, int n, List<Integer> result) {
        if (current > n) return;
        result.add(current);
        for (int i = 0; i <= 9; ++i) {
            if (current * 10 + i > n) return;
            dfs(current * 10 + i, n, result);
        }
    }

    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i < 10; ++i) {
            dfs(i, n, result);
        }
        return result;
    }

    public static void main(String[] args) {
        LexicalOrderDFS obj = new LexicalOrderDFS();
        int n = 13;
        List<Integer> result = obj.lexicalOrder(n);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

void dfs(int current, int n, vector<int>& result) {
    if (current > n) return;
    result.push_back(current);
    for (int i = 0; i <= 9; ++i) {
        if (current * 10 + i > n) return;
        dfs(current * 10 + i, n, result);
    }
}

vector<int> lexicalOrder(int n) {
    vector<int> result;
    for (int i = 1; i < 10; ++i) {
        dfs(i, n, result);
    }
    return result;
}

int main() {
    int n = 13;
    vector<int> result = lexicalOrder(n);
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

JavaScript

const dfs = (current, n, result) => {
    if (current > n) return;
    result.push(current);
    for (let i = 0; i <= 9; i++) {
        if (current * 10 + i > n) return;
        dfs(current * 10 + i, n, result);
    }
};

const lexicalOrder = (n) => {
    const result = [];
    for (let i = 1; i < 10; i++) {
        dfs(i, n, result);
    }
    return result;
};

const n = 13;
console.log(lexicalOrder(n));

#include <stdio.h>

void dfs(int current, int n, int* result, int* index) {
    if (current > n) return;
    result[(*index)++] = current;
    for (int i = 0; i <= 9; ++i) {
        if (current * 10 + i > n) return;
        dfs(current * 10 + i, n, result, index);
    }
}

int* lexicalOrder(int n, int* returnSize) {
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = 0;
    for (int i = 1; i < 10; ++i) {
        dfs(i, n, result, returnSize);
    }
    return result;
}

int main() {
    int n = 13;
    int returnSize;
    int* result = lexicalOrder(n, &returnSize);
    for (int i = 0; i < returnSize; ++i) {
        printf("%d ", result[i]);
    }
    free(result);
    return 0;
}

using System;
using System.Collections.Generic;

public class LexicalOrderDFS {
    public void DFS(int current, int n, IList<int> result) {
        if (current > n) return;
        result.Add(current);
        for (int i = 0; i <= 9; ++i) {
            if (current * 10 + i > n) return;
            DFS(current * 10 + i, n, result);
        }
    }

    public IList<int> LexicalOrder(int n) {
        IList<int> result = new List<int>();
        for (int i = 1; i < 10; ++i) {
            DFS(i, n, result);
        }
        return result;
    }

    public static void Main(string[] args) {
        LexicalOrderDFS obj = new LexicalOrderDFS();
        int n = 13;
        IList<int> result = obj.LexicalOrder(n);
        foreach (int num in result) {
            Console.Write(num + " ");
        }
    }
}

This Python implementation leverages a result list and recursively calls dfs to append lexicographically ordered numbers until the bounds are met.

Complexity

Time Complexity: O(n), Space Complexity: O(1) (excluding the output list).

Try this approach in the editor

Approach 2: Iterative Approach

This iterative approach attempts to simulate the depth-first search behavior using an iterative procedure. It begins by using a number and incrementally moving to the next lexicographical number by clever digit manipulations. If a number reaches an immediate boundary, it backs off accordingly to stay within valid digits.

Python

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

n = 13
print(lexicalOrder(n))

Java

import java.util.ArrayList;
import java.util.List;

public class IterativeLexicalOrder {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> result = new ArrayList<>();
        int num = 1;
        for (int i = 0; i < n; ++i) {
            result.add(num);
            if (num * 10 <= n) {
                num *= 10;
            } else {
                while (num % 10 == 9 || num + 1 > n) {
                    num /= 10;
                }
                num++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        IterativeLexicalOrder obj = new IterativeLexicalOrder();
        int n = 13;
        List<Integer> result = obj.lexicalOrder(n);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

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

int main() {
    int n = 13;
    vector<int> result = lexicalOrder(n);
    for (int num : result) {
        cout << num << " ";
    }
    return 0;
}

JavaScript

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

const n = 13;
console.log(lexicalOrder(n));

#include <stdio.h>
#include <stdlib.h>

int* lexicalOrder(int n, int* returnSize) {
    int* result = (int*)malloc(n * sizeof(int));
    *returnSize = 0;
    int num = 1;
    for (int i = 0; i < n; i++) {
        result[(*returnSize)++] = num;
        if (num * 10 <= n) {
            num *= 10;
        } else {
            while (num % 10 == 9 || num + 1 > n) {
                num /= 10;
            }
            num++;
        }
    }
    return result;
}

int main() {
    int n = 13;
    int returnSize;
    int* result = lexicalOrder(n, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", result[i]);
    }
    free(result);
    return 0;
}

using System;
using System.Collections.Generic;

public class IterativeLexicalOrder {
    public IList<int> LexicalOrder(int n) {
        IList<int> result = new List<int>();
        int num = 1;
        for (int i = 0; i < n; ++i) {
            result.Add(num);
            if (num * 10 <= n) {
                num *= 10;
            } else {
                while (num % 10 == 9 || num + 1 > n) {
                    num /= 10;
                }
                num++;
            }
        }
        return result;
    }

    public static void Main(string[] args) {
        IterativeLexicalOrder obj = new IterativeLexicalOrder();
        int n = 13;
        IList<int> result = obj.LexicalOrder(n);
        foreach (int num in result) {
            Console.Write(num + " ");
        }
    }
}

This Python solution iteratively advances through potential numerals with respect to the current value and known boundaries, producing a sequence of numbers sorted lexicographically.

Complexity

Time Complexity: O(n), Space Complexity: O(1) (ignoring list storage).

Try this approach in the editor

Approach 3: Iteration

We first define a variable v, initially v = 1. Then we start iterating from 1, adding v to the answer array each time. Then, if v times 10 leq n, we update v to v times 10; otherwise, if v bmod 10 = 9 or v + 1 > n, we loop to divide v by 10. After the loop ends, we increment v. Continue iterating until we have added n numbers to the answer array.

The time complexity is O(n), where n is the given integer n. Ignoring the space consumption of the answer array, the space complexity is O(1).

TypeScript

function lexicalOrder(n: number): number[] {
    const ans: number[] = [];
    let v = 1;
    for (let i = 0; i < n; ++i) {
        ans.push(v);
        if (v * 10 <= n) {
            v *= 10;
        } else {
            while (v % 10 === 9 || v === n) {
                v = Math.floor(v / 10);
            }
            ++v;
        }
    }
    return ans;
}

func lexicalOrder(n int) (ans []int) {
	v := 1
	for i := 0; i < n; i++ {
		ans = append(ans, v)
		if v*10 <= n {
			v *= 10
		} else {
			for v%10 == 9 || v+1 > n {
				v /= 10
			}
			v++
		}
	}
	return
}

Rust

impl Solution {
    pub fn lexical_order(n: i32) -> Vec<i32> {
        let mut ans = Vec::with_capacity(n as usize);
        let mut v = 1;
        for _ in 0..n {
            ans.push(v);
            if v * 10 <= n {
                v *= 10;
            } else {
                while v % 10 == 9 || v + 1 > n {
                    v /= 10;
                }
                v += 1;
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
DFS Approach	Time Complexity: O(n), Space Complexity: O(1) (excluding the output list).
Iterative Approach	Time Complexity: O(n), Space Complexity: O(1) (ignoring list storage).
Iteration	–

Complexity analysis

Approach	Time	Space	When to Use
DFS Prefix Traversal	O(n)	O(h) recursion stack	When you want a clear conceptual mapping to a trie or DFS traversal of prefixes
Iterative Lexicographical Traversal	O(n)	O(1) extra space	Preferred for interviews and production due to constant space and direct traversal

Frequently asked questions

Is Lexicographical Numbers easy or hard?

Lexicographical Numbers is rated Medium on LeetCode. The difficulty comes from recognizing the implicit trie structure and generating lexicographical order without sorting strings, which requires careful prefix traversal logic.

Lexicographical Numbers Python/Java solution

Python and Java implementations typically follow either DFS recursion or an iterative prefix traversal. Both solutions maintain O(n) time complexity. The iterative version is popular in interviews because it avoids recursion and uses constant extra space.

How to solve Lexicographical Numbers in O(n)?

Treat numbers as prefixes of a virtual trie. Start from 1 and repeatedly go deeper by multiplying by 10 when possible. If not possible, move to the next sibling by incrementing the number, and backtrack by dividing by 10 when the prefix exceeds n. This visits each number once, achieving O(n) time.

What is the best approach for Lexicographical Numbers?

The best approach is iterative lexicographical traversal, which simulates walking through a prefix tree. It generates numbers from 1 to n in dictionary order using arithmetic operations like *10, +1, and /10. This solution runs in O(n) time with O(1) extra space.

Is Lexicographical Numbers asked at Google/Amazon/Meta?

Lexicographical ordering and prefix traversal problems appear in interviews at companies like Google, Amazon, and Meta, especially in questions related to tries or number generation patterns. The problem tests understanding of DFS-style traversal and efficient iteration without sorting.

What data structure is used in Lexicographical Numbers?

The problem conceptually uses a Trie (prefix tree). Each digit extension represents moving to a child node. The DFS approach explicitly mimics trie traversal, while the iterative approach navigates the same structure using arithmetic operations instead of building the tree.

What is the time complexity of Lexicographical Numbers?

Both common solutions run in O(n) time because each number from 1 to n is processed exactly once. The DFS approach uses O(h) auxiliary space for recursion where h is the number of digits in n, while the iterative method uses O(1) extra space.

Lexicographical Numbers solution and explanation

The problem

Approach overview

Approach 1: DFS Approach

Approach 2: Iterative Approach

Approach 3: Iteration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Lexicographical Numbers solution and explanation

The problem

Approach overview

Approach 1: DFS Approach

Approach 2: Iterative Approach

Approach 3: Iteration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems