Lexicographical Numbers - Leetcode Solution

Problem Statement:

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

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

Solution:

The problem can be solved by generating lexicographically sorted numbers starting from 1 using DFS (Depth-First Search) and adding them to the result until we reach n. In each iteration, we will recursively generate all children of the current node (which is the last number in the previous iteration) until we reach n.

For example, let's take n = 25. We start with 1, then we generate its children 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, and 2 (because we need to generate all the children before moving to the next node). Then, for each of these children, we recursively generate their children until we reach n. The order of children is important because we need to generate them in lexicographical order.

To implement this, we will use a stack data structure to keep track of the current number and its children. We will start with 1 and push it into the stack. Then, we will enter a loop until the stack is empty or we have found all the numbers up to n. In each iteration, we will pop the top element from the stack and add it to the result if it is less than or equal to n. Then, we will generate all its children (in lexicographical order) and push them into the stack.

The children are generated in the following way:

If the current number is less than n, we add a zero to the end of it and generate a new number (example: from 10, we generate 100). If the current number is less than n and its last digit is not 9, we increment the last digit and generate a new number (example: from 19, we generate 20). If the current number is greater than or equal to n, we don't generate any children.

The implementation is given below:

class Solution { public: vector<int> lexicalOrder(int n) { vector<int> res; stack<int> s; for (int i = min(n, 9); i >= 1; i--) { if (i <= n) { s.push(i); } } while (!s.empty()) { int num = s.top(); s.pop(); res.push_back(num); for (int i = min(n, num * 10 + 9); i >= num * 10; i--) { if (i <= n) { s.push(i); } } } return res; } };

Analysis:

The time complexity of this algorithm is O(n) because we generate all numbers up to n once. The space complexity is O(log n) because the maximum depth of the stack is log(n), which is the number of digits in n.

Conclusion:

The lexicographical numbers problem can be solved by generating lexicographically sorted numbers starting from 1 using DFS. We use a stack data structure to keep track of the current number and its children. The children are generated in lexicographical order, and the algorithm stops when we have found all the numbers up to n. The time complexity of this algorithm is O(n), and the space complexity is O(log n).

1