Lexicographical Numbers - Practice Coding Problems

Lexicographical Numbers - Problem

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

Lexicographical order means the numbers are sorted as if they were strings. For example, [1, 10, 11, 2, 3] would be the lexicographical order for numbers 1-11.

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

Input & Output

Example 1 — Basic Case

$ Input: n = 13

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

💡 Note: Numbers 1-13 in lexicographical order: 1 comes first, then 10,11,12,13 (all start with '1'), then 2,3,4,5,6,7,8,9

Example 2 — Small Range

$ Input: n = 2

› Output: [1,2]

💡 Note: Only two numbers: 1 and 2, already in lexicographical order

Example 3 — Powers of 10

$ Input: n = 100

› Output: [1,10,100,11,12,13,...,19,2,20,21,...,99]

💡 Note: Starts with 1, then all numbers beginning with '1' (10,100,11,12...19), then numbers starting with '2', etc.

Constraints

1 ≤ n ≤ 5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Range [1, n] where n=13

Process

Sort as if numbers were strings

Output

Numbers in dictionary order

Key Takeaway

🎯 Key Insight: Numbers form a tree structure where DFS traversal naturally produces lexicographical order

Asked in

G Google 25 a Amazon 20 f Facebook 15 M Microsoft 12

The key insight is treating numbers as nodes in a 10-ary tree where DFS naturally produces lexicographical order. The optimal iterative DFS approach achieves O(n) time and O(1) space by simulating tree traversal without recursion stack.

Common Approaches

Approach	Time	Space	Notes
✓ Generate and Sort	O(n log n)	O(n)	Generate all numbers as strings and sort them lexicographically
Iterative DFS (O(1) Space)	O(n)	O(1)	Simulate DFS iteratively to achieve O(1) extra space
DFS Tree Traversal	O(n)	O(log n)	Treat numbers as nodes in a 10-ary tree and perform DFS

Generate and Sort — Algorithm Steps

Step 1: Generate all numbers from 1 to n
Step 2: Convert each number to string
Step 3: Sort strings lexicographically
Step 4: Convert back to integers

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create numbers 1 to n

Convert

Convert to strings for comparison

Sort

Sort strings lexicographically

Code -

solution.c — C

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

int compare(const void *a, const void *b) {
    return strcmp(*(char**)a, *(char**)b);
}

int* solution(int n, int* returnSize) {
    char** numbers = (char**)malloc(n * sizeof(char*));
    
    // Generate all numbers and convert to strings
    for (int i = 1; i <= n; i++) {
        numbers[i-1] = (char*)malloc(12 * sizeof(char));
        sprintf(numbers[i-1], "%d", i);
    }
    
    // Sort lexicographically
    qsort(numbers, n, sizeof(char*), compare);
    
    // Convert back to integers
    int* result = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = atoi(numbers[i]);
        free(numbers[i]);
    }
    free(numbers);
    
    *returnSize = n;
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int returnSize;
    int* result = solution(n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting n strings takes O(n log n) time

⚡ Linearithmic

Space Complexity

O(n)

Storing n string representations of numbers

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate and Sort — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler