LC-0386 Medium LeetCode

386. Lexicographical Numbers

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 73% Topics: Depth-First Search, Trie

Reading material

Trees & Traversals 18 min Tries (Prefix Trees) 10 min

Reference solution (spoiler · python)

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

class Solution(object):
    def lexicalOrder(self, n):
        result = []

        i = 1
        while len(result) < n:
            k = 0
            while i * 10**k <= n:
                result.append(i * 10**k)
                k += 1

            num = result[-1] + 1
            while num <= n and num % 10:
                result.append(num)
                num += 1

            if not num % 10:
                num -= 1
            else:
                num /= 10

            while num % 10 == 9:
                num /= 10

            i = num+1

        return result

Solution from kamyu104/LeetCode-Solutions · MIT