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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lexicographical Numbers

Difficulty: Medium

Problem Description

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

Key Insights

  • Lexicographical order is similar to dictionary order where numbers are sorted based on their string representation.
  • A depth-first search (DFS) approach can be used to generate numbers in the correct order by exploring each number node.
  • The algorithm must be efficient, operating in O(n) time and using O(1) extra space.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The problem can be solved using a depth-first search (DFS) strategy. The idea is to generate numbers starting from 1 and explore each number by appending digits (0-9) while ensuring we do not exceed n. This ensures that we traverse the numbers in lexicographical order. We store the results in a list and return it at the end.

Code Solutions

def lexicalOrder(n):
    result = []
    
    def dfs(current):
        if current > n:
            return
        result.append(current)
        for i in range(10):
            next_num = current * 10 + i
            if next_num > n:
                break
            dfs(next_num)

    for i in range(1, 10):
        if i > n:
            break
        dfs(i)

    return result
← Back to All Questions