Jobs

Interviews

Discussions

Lexicographical Numbers

Medium

Asked by:

More companies

77 views

Topics:

Recursion

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⁴

Try coding it in LeetCode

Lexicographical Numbers

Medium

Asked by:

77 views

Topics:

Recursion

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⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `n`? This will help me determine the appropriate data types and consider potential overflow issues.
Should the returned array contain numbers as strings or integers? Although the problem states integers, confirming the desired output type is crucial.
If `n` is less than 1, should I return an empty array, or is there a minimum acceptable value for `n`?
Are there any specific memory constraints I should be aware of, given that the output array will have `n` elements?
Could you provide a small example with n = 12 to confirm my understanding of lexicographical order in this context?

Brute Force Solution

Approach

To list numbers in lexicographical order, think of it like organizing words in a dictionary. The brute force method is to simply create all possible numbers within the given range and then sort them based on their dictionary order.

Here's how the algorithm would work step-by-step:

First, create a list containing all whole numbers from 1 up to the given limit.
Next, compare the numbers in the list as if they were words in a dictionary to figure out their order.
For example, '1' comes before '10' because '1' starts with '1' and '10' also starts with '1', but then '10' has another digit which makes it later in dictionary order.
Arrange the list so that the numbers appear in the correct dictionary order.
Finally, you have the numbers listed in lexicographical order.

Code Implementation

def lexicographical_numbers_brute_force(maximum_number):
    # Create a list of numbers from 1 to maximum_number
    numbers_list = list(range(1, maximum_number + 1))

    # Sort the list lexicographically
    numbers_list.sort(key=str)

    # Ensure the result is returned
    return numbers_list

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first generates n numbers from 1 to the input value. Then, it sorts these n numbers lexicographically. Sorting typically uses comparison-based algorithms with a time complexity of O(n log n), where each comparison involves comparing the string representations of the numbers. Therefore, the overall time complexity is dominated by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The provided algorithm creates a list containing all whole numbers from 1 up to the given limit N. This list stores N integer values. Therefore, the auxiliary space required is proportional to the input size N. This can be simplified to O(N).

Optimal Solution

Approach

The goal is to create a list of numbers in lexicographical order (like a dictionary) up to a certain limit. The efficient way is to build the numbers one digit at a time, prioritizing depth-first exploration to follow the lexicographical order.

Here's how the algorithm would work step-by-step:

Start with the number 1.
Add this number to our list.
Check if multiplying the current number by 10 (adding a zero to the end) still keeps us below the given limit. If it does, this becomes our new current number and we add this new number to the list. We essentially dive deeper.
If adding a zero makes the number too big, or if the current number ends in 9, we need to go back and try incrementing the current number. Increment the number. If the number becomes larger than the limit after the increment, then we are done.
Before adding the incremented number, check if the rightmost digit is zero. If it is, this indicates we went back up a level and we want to keep going up levels until we reach the root, and then increment. Removing the zero from the number until the last digit is not zero and try incrementing after removing all zeroes.
Repeat steps 2-5 until all lexicographical numbers under the limit have been generated.

Code Implementation

def lexicographical_numbers(limit):    result = []
    current_number = 1

    while current_number <= limit:
        result.append(current_number)

        # Dive deeper by multiplying by 10 if possible
        if current_number * 10 <= limit:
            current_number *= 10

        else:
            # Go back and increment if can't dive deeper
            if current_number >= limit:
                break

            current_number += 1

            # Keep incrementing until the last digit is not zero
            while current_number % 10 == 0:

                current_number //= 10
            # Prevents going over limit
            if current_number > limit:
              break
    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm generates n numbers in lexicographical order. For each number generated, the operations involve multiplication by 10, incrementing by 1, and potentially repeatedly dividing by 10 to trim trailing zeros. Each of these operations takes constant time. Since we generate n numbers with constant time operations for each, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm primarily uses a few integer variables to track the current number being generated. The only auxiliary space is for storing the result list, but the space complexity analysis asks for ONLY auxiliary space. The space to store the result list is not part of the algorithm's auxiliary space. Therefore, the auxiliary space remains constant regardless of the input limit N, leading to a space complexity of O(1).

Edge Cases

Case	How to Handle
n is 0	Return an empty list because the problem asks for numbers from 1 to n.
n is a single digit number (1-9)	The solution should correctly generate the list [1, 2, ..., n].
n is a power of 10 (e.g., 10, 100, 1000)	Ensure the solution handles the transition from 9 to 10, 99 to 100, etc., correctly in lexicographical order.
n is a large number (close to Integer.MAX_VALUE in Java)	The solution should be efficient enough to avoid timeouts; iterative deepening is suggested.
The lexicographical order exceeds the maximum integer value	The code must terminate traversal when the generated number is greater than n.
n contains leading zeros (should be handled as a valid integer)	The problem statement implies input is a valid integer, so leading zeros are not applicable.
All numbers from 1 to n have the same starting digit.	The recursion or iteration explores all subtrees fully, ensuring correct lexicographical order despite the common prefix.
n is a number like 111111, and many numbers have a long shared prefix.	The solution needs to avoid excessive recursion depth or unnecessary computations due to the long shared prefix.

n is 0

How to Handle:

Return an empty list because the problem asks for numbers from 1 to n.

n is a single digit number (1-9)

How to Handle:

The solution should correctly generate the list [1, 2, ..., n].

n is a power of 10 (e.g., 10, 100, 1000)

How to Handle:

Ensure the solution handles the transition from 9 to 10, 99 to 100, etc., correctly in lexicographical order.

n is a large number (close to Integer.MAX_VALUE in Java)

How to Handle:

The solution should be efficient enough to avoid timeouts; iterative deepening is suggested.

The lexicographical order exceeds the maximum integer value

How to Handle:

The code must terminate traversal when the generated number is greater than n.

n contains leading zeros (should be handled as a valid integer)

How to Handle:

The problem statement implies input is a valid integer, so leading zeros are not applicable.

All numbers from 1 to n have the same starting digit.

How to Handle:

The recursion or iteration explores all subtrees fully, ensuring correct lexicographical order despite the common prefix.

n is a number like 111111, and many numbers have a long shared prefix.

How to Handle:

The solution needs to avoid excessive recursion depth or unnecessary computations due to the long shared prefix.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of `n`? This will help me determine the appropriate data types and consider potential overflow issues.
Should the returned array contain numbers as strings or integers? Although the problem states integers, confirming the desired output type is crucial.
If `n` is less than 1, should I return an empty array, or is there a minimum acceptable value for `n`?
Are there any specific memory constraints I should be aware of, given that the output array will have `n` elements?
Could you provide a small example with n = 12 to confirm my understanding of lexicographical order in this context?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a list containing all whole numbers from 1 up to the given limit.
Next, compare the numbers in the list as if they were words in a dictionary to figure out their order.
For example, '1' comes before '10' because '1' starts with '1' and '10' also starts with '1', but then '10' has another digit which makes it later in dictionary order.
Arrange the list so that the numbers appear in the correct dictionary order.
Finally, you have the numbers listed in lexicographical order.

Code Implementation

def lexicographical_numbers_brute_force(maximum_number):
    # Create a list of numbers from 1 to maximum_number
    numbers_list = list(range(1, maximum_number + 1))

    # Sort the list lexicographically
    numbers_list.sort(key=str)

    # Ensure the result is returned
    return numbers_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 1.
Add this number to our list.
Check if multiplying the current number by 10 (adding a zero to the end) still keeps us below the given limit. If it does, this becomes our new current number and we add this new number to the list. We essentially dive deeper.
If adding a zero makes the number too big, or if the current number ends in 9, we need to go back and try incrementing the current number. Increment the number. If the number becomes larger than the limit after the increment, then we are done.
Before adding the incremented number, check if the rightmost digit is zero. If it is, this indicates we went back up a level and we want to keep going up levels until we reach the root, and then increment. Removing the zero from the number until the last digit is not zero and try incrementing after removing all zeroes.
Repeat steps 2-5 until all lexicographical numbers under the limit have been generated.

Code Implementation

def lexicographical_numbers(limit):    result = []
    current_number = 1

    while current_number <= limit:
        result.append(current_number)

        # Dive deeper by multiplying by 10 if possible
        if current_number * 10 <= limit:
            current_number *= 10

        else:
            # Go back and increment if can't dive deeper
            if current_number >= limit:
                break

            current_number += 1

            # Keep incrementing until the last digit is not zero
            while current_number % 10 == 0:

                current_number //= 10
            # Prevents going over limit
            if current_number > limit:
              break
    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 0	Return an empty list because the problem asks for numbers from 1 to n.
n is a single digit number (1-9)	The solution should correctly generate the list [1, 2, ..., n].
n is a power of 10 (e.g., 10, 100, 1000)	Ensure the solution handles the transition from 9 to 10, 99 to 100, etc., correctly in lexicographical order.
n is a large number (close to Integer.MAX_VALUE in Java)	The solution should be efficient enough to avoid timeouts; iterative deepening is suggested.
The lexicographical order exceeds the maximum integer value	The code must terminate traversal when the generated number is greater than n.
n contains leading zeros (should be handled as a valid integer)	The problem statement implies input is a valid integer, so leading zeros are not applicable.
All numbers from 1 to n have the same starting digit.	The recursion or iteration explores all subtrees fully, ensuring correct lexicographical order despite the common prefix.
n is a number like 111111, and many numbers have a long shared prefix.	The solution needs to avoid excessive recursion depth or unnecessary computations due to the long shared prefix.

n is 0

How to Handle:

Return an empty list because the problem asks for numbers from 1 to n.

n is a single digit number (1-9)

How to Handle:

The solution should correctly generate the list [1, 2, ..., n].

n is a power of 10 (e.g., 10, 100, 1000)

How to Handle:

Ensure the solution handles the transition from 9 to 10, 99 to 100, etc., correctly in lexicographical order.

n is a large number (close to Integer.MAX_VALUE in Java)

How to Handle:

The solution should be efficient enough to avoid timeouts; iterative deepening is suggested.

The lexicographical order exceeds the maximum integer value

How to Handle:

The code must terminate traversal when the generated number is greater than n.

n contains leading zeros (should be handled as a valid integer)

How to Handle:

The problem statement implies input is a valid integer, so leading zeros are not applicable.

All numbers from 1 to n have the same starting digit.

How to Handle:

The recursion or iteration explores all subtrees fully, ensuring correct lexicographical order despite the common prefix.

n is a number like 111111, and many numbers have a long shared prefix.

How to Handle:

The solution needs to avoid excessive recursion depth or unnecessary computations due to the long shared prefix.