We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lexicographical Numbers

Number: 386

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta, Barclays, TikTok, Bloomberg

Problem Description

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical (dictionary) order. The algorithm should run in O(n) time and use O(1) extra space.

Key Insights

  • The lexicographical order is similar to how words are sorted in a dictionary.
  • A depth-first traversal approach can generate the sequence without using additional space for storing intermediate results (aside from the output list).
  • The trick: Start from 1 and try to go as deep as possible by multiplying by 10; if that is not possible, try to increase the current number by 1.
  • When reaching a dead-end (i.e., when the next number would exceed n or the last digit is 9), backtrack by dividing by 10 until you can increment safely.

Space and Time Complexity

Time Complexity: O(n) - Each number from 1 to n is generated exactly once. Space Complexity: O(1) - No extra space is used apart from the output list (ignoring recursion stack/constant pointers).

Solution

We use an iterative depth-first search (DFS) style approach:

  1. Start with the number 1.
  2. For each number appended in the result:
    • If multiplying the current number by 10 does not cause the number to exceed n, move downward in the lexicographical tree by setting current = current * 10.
    • Otherwise, if the current number is not at the end of a branch (i.e., its last digit isn’t 9) and adding 1 does not exceed n, simply increment current by 1.
    • If neither move is possible, repeatedly backtrack by dividing the current number by 10 until we can increment until the next valid number.
  3. Continue until all numbers up to n are added.

This process mimics a DFS on a virtual tree where each node represents a number. The left-most branch (multiplying by 10) gives lexicographically smaller numbers, while the right siblings come from adding 1. The algorithm avoids extra space by directly computing the next value from the current number.

Code Solutions

# Function to generate lexicographical numbers.
def lexicalOrder(n):
    # Initialize the result list and start with the first number.
    result = []
    current = 1
    # Loop for each number from 1 to n.
    for _ in range(n):
        result.append(current)  # Append current number to result.
        # If next lexicographical number can be obtained by going down one level.
        if current * 10 <= n:
            current *= 10  # Move to the next level (append 0 at the end).
        else:
            # If we cannot go down, then increment.
            # If current ends in 9 or incrementing exceeds n, we need to backtrack.
            if current >= n:
                # Backtrack until you can increment.
                while current % 10 == 9 or current == n:
                    current //= 10
            current += 1  # Try the next number.
    return result

# Example usage:
print(lexicalOrder(13))
← Back to All Questions