• Posts

Problem 386 Lexicographical Numbers

Problem Statement

Link - Problem 386

Question

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 * 104

Solution

class Solution {
public:
struct Node{
    Node* links[10];
    bool flag=false;
    bool containsKey(char ch){
        return links[ch-'0']!=NULL;
    }
    void put(char ch, Node* node){
        links[ch-'0'] = node;
    }
    Node* get(char ch){
        return links[ch-'0'];
    }
    void setEnd(){
        flag = true;
    }
    bool getEnd(){
        return flag;
    }
};
class Trie{
public:
    Node* root;

    Trie(){
        root = new Node();
    }
    void insert(string& num){
        Node* temp = root;
        for(int i=0; i<num.size(); i++){
            if(!temp->containsKey(num[i])){
                temp->put(num[i], new Node());
            }
            temp = temp->get(num[i]);
        }
        temp->setEnd();
    }
};

    void dfs(Node* root, int curr, vector<int>& ans){
        if(root==NULL){
            return;
        }
        if(root->getEnd()==true){
            ans.push_back(curr);
        }
        for(char ch='0'; ch<='9'; ch++){
            if(root->containsKey(ch)){
                dfs(root->get(ch), (curr*10)+(ch-'0'), ans);
            }
        }
    }

    vector<int> lexicalOrder(int n) {
        std::ios::sync_with_stdio(false);
        Trie trie;
        for(int i=1; i<=n; i++){
            string s = to_string(i);
            trie.insert(s);
        }

        vector<int> ans;
        dfs(trie.root,0,ans);
        return ans;
    }
};

Complexity Analysis

| Algorithm                    | Time Complexity | Space Complexity |
| ---------------------------- | --------------- | ---------------- |
| Trie with Depth-first Search | O(n log n)      | O(n log n)       |

Explanation

Intial Thoughts

To start, we should consider how numbers are sorted in lexicographical order. We can think of it like arranging words in a dictionary, where each digit position acts like a letter. We also need to find an approach that allows us to generate these numbers in the given time and space complexity. We should list the key constraints and try to find patterns or relationships between the numbers. Breaking down the problem into smaller parts, like understanding how to generate the numbers and how to ensure lexicographical order, can be helpful.

Intuitive Analysis

When solving this problem intuitively, we can start by thinking about how we would arrange these numbers manually. We can consider what would happen if we started with the smallest number and thought about how to generate the next one in lexicographical order. Using a tree or a similar data structure might be helpful in visualizing this process and generating all the possible numbers. Additionally, thinking about how to use the given constraints to limit the search space and ensure efficiency can help us to develop an effective solution strategy. Considering the use of a Trie data structure to organize the numbers and a depth-first search to find all the numbers in lexicographical order could also be a good approach.

1. Intuition

• The problem requires generating numbers in lexicographical order, which suggests a string-based comparison approach
• A Trie data structure can be used to store and retrieve numbers in lexicographical order
• The Trie allows for efficient insertion and traversal of numbers, making it suitable for this problem
• The key insight is to treat numbers as strings and use the Trie to store and retrieve them
• This approach works because the Trie ensures that numbers are stored and retrieved in lexicographical order
• The algorithmic choice of using a Trie and depth-first search (DFS) allows for efficient generation of numbers in lexicographical order
• The use of DFS enables the algorithm to traverse the Trie and generate numbers in the correct order

2. Implementation

• The Trie class is used to store numbers as strings, with each node representing a digit in the number
• The insert method is used to insert numbers into the Trie, with each digit being added as a new node
• The dfs function is used to traverse the Trie and generate numbers in lexicographical order, using the root node and curr value to keep track of the current number
• The lexicalOrder function uses the Trie and DFS to generate numbers in lexicographical order, starting from 1 and ending at n
• The std::ios::sync_with_stdio(false) line is used to improve performance by disabling synchronization with C-style input/output
• The to_string(i) function is used to convert each number to a string, allowing it to be inserted into the Trie
• The ans vector is used to store the generated numbers in lexicographical order, which is then returned as the result

Complexity Analysis

Time Complexity:

• The time complexity is O(n log n) because for each number from 1 to n, we are converting it to a string using to_string(i) and then inserting it into the Trie, which takes O(log n) time. The dfs function is called once on the root of the Trie and its time complexity is also proportional to the number of nodes in the Trie, which is O(n log n).
• The dominant operations are the insert function which is called n times and the dfs function which visits each node in the Trie once. Each insert operation takes O(log n) time because in the worst case, we are creating a new path of length log n in the Trie.
• The Big O classification is justified because the time complexity is linear with respect to the number of input elements (n) and logarithmic with respect to the size of each input element (log n).

Space Complexity:

• The space complexity is O(n log n) because in the worst case, we are storing all numbers from 1 to n in the Trie. Each number is represented as a string of maximum length log n and we are storing it in the links array of each node.
• The Trie data structure has a significant impact on the space complexity because each node in the Trie can have up to 10 children (one for each digit from 0 to 9) and each child node can have its own children. This results in a large number of nodes being created, especially for large values of n.
• The space complexity is justified because the amount of memory used is directly proportional to the number of input elements (n) and the size of each input element (log n).

Footnote

This question is rated as Medium difficulty.