Leetcode 386: Lexicographical Numbers

Input: The input consists of a single integer n.

Example: n = 15

Constraints:

• 1 <= n <= 50,000

Output: Return a list of integers from 1 to n, sorted in lexicographical order.

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

Constraints:

• The output should contain all the numbers from 1 to n, sorted lexicographically.

Goal: The goal is to generate the numbers in lexicographical order without storing the entire list upfront and while maintaining an efficient time complexity.

Steps:

• Start from 1 and recursively append the next lexicographically smaller number.

• For each number, attempt to add a zero to make it a 'child' of the current number.

• If the current number exceeds n, backtrack to the next number in the sequence.

Goal: The algorithm should be efficient both in terms of time and space.

Steps:

• Time complexity should be O(n).

• Space complexity should be O(1) additional space, aside from the space required for the result.

Assumptions:

• The input value n is valid and lies within the specified range.

• Input: Input: 15

• Explanation: The lexicographical order of the numbers from 1 to 15 is: 1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9.

Approach: The approach is to generate the numbers in lexicographical order by recursively trying to append digits to the current number. The recursion will be stopped when a number exceeds n.

Observations:

• We need to find a way to generate the numbers in lexicographical order without directly sorting the entire list.

• We can perform a depth-first search (DFS) from 1, appending digits to form lexicographically smaller numbers.

Steps:

• Start at 1, and recursively try to multiply the current number by 10.

• If the current number exceeds n, backtrack and move to the next number in the sequence.

• Ensure the algorithm runs efficiently with O(n) time and O(1) extra space.

Empty Inputs:

• Input will always be a valid positive integer as per constraints.

Large Inputs:

• Ensure that the algorithm handles large values of n (up to 50,000) efficiently.

Special Values:

• For n = 1, the output is simply [1].

Constraints:

• The algorithm should generate the numbers in lexicographical order efficiently.

int num;
vector<int> ans;
vector<int> lexicalOrder(int n) {
    num = n;
    d(1);
    return ans;
}
void d(int x) {
    if(x > num) return;
    ans.push_back(x);
    d(x * 10);
    if((x % 10) < 9) d(x + 1);
}

1 : Variable Declaration

int num;

Declare a global variable 'num' that will store the value of 'n'.

2 : Variable Declaration

vector<int> ans;

Declare a vector 'ans' to store the numbers in lexicographical order.

3 : Function Definition

vector<int> lexicalOrder(int n) {

Define the main function 'lexicalOrder' which takes an integer 'n' as input and returns a vector of integers in lexicographical order.

4 : Assignment

    num = n;

Assign the value of 'n' to the global variable 'num'.

5 : Function Call

    d(1);

Call the recursive function 'd' with the starting value 1.

6 : Return Statement

    return ans;

Return the vector 'ans' containing the lexicographically ordered numbers.

7 : Function Definition

void d(int x) {

Define a helper function 'd' which takes an integer 'x' and recursively generates numbers in lexicographical order.

8 : Base Case

    if(x > num) return;

If the current number 'x' exceeds 'num', return and stop the recursion.

9 : Push Operation

    ans.push_back(x);

Add the current number 'x' to the vector 'ans'.

10 : Recursive Call

    d(x * 10);

Recursively call 'd' with 'x * 10', which generates the next level of lexicographical numbers.

11 : Condition Check

    if((x % 10) < 9) d(x + 1);

If the current number 'x' is not ending in 9, call 'd' with 'x + 1' to explore the next number.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is linear because we generate each number exactly once.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is constant, aside from the space required to store the result.

Leetcode 386: Lexicographical Numbers

Solution to LeetCode 386: Lexicographical Numbers Problem

Explore →