How hard is LeetCode 440. K-th Smallest in Lexicographical Order?

LeetCode 440. K-th Smallest in Lexicographical Order is rated Hard on LeetCode.

What is the time complexity of LeetCode 440. K-th Smallest in Lexicographical Order?

The Python solution on this page runs in O(\log^2 n), as we perform logarithmic operations for counting and traversing the Trie structure.

What is the space complexity of LeetCode 440. K-th Smallest in Lexicographical Order?

The Python solution on this page uses O(1) since we only use a few variables to track the current prefix and count auxiliary space.

What topics does LeetCode 440. K-th Smallest in Lexicographical Order cover?

LeetCode 440. K-th Smallest in Lexicographical Order is tagged Trie on LeetCode.

K-th Smallest in Lexicographical Order — LeetCode 440 Python Solution

HardTrie

Problem: #440
Pattern: Trie
Reading time: 4 min
Source: leetcode.com

The problem

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

Example

Input: n = 13, k = 2
Output: 10
Explanation: The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Python solution

Python

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count(curr):
            next, cnt = curr + 1, 0
            while curr <= n:
                cnt += min(n - curr + 1, next - curr)
                next, curr = next * 10, curr * 10
            return cnt

        curr = 1
        k -= 1
        while k:
            cnt = count(curr)
            if k >= cnt:
                k -= cnt
                curr += 1
            else:
                k -= 1
                curr *= 10
        return curr

Complexity

Measure	Complexity
Time	O(\log^2 n), as we perform logarithmic operations for counting and traversing the Trie structure
Space	O(1) since we only use a few variables to track the current prefix and count auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 440. K-th Smallest in Lexicographical Order is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Trie.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 440. K-th Smallest in Lexicographical Order?: LeetCode 440. K-th Smallest in Lexicographical Order is rated Hard on LeetCode.
What is the time complexity of LeetCode 440. K-th Smallest in Lexicographical Order?: The Python solution on this page runs in O(\log^2 n), as we perform logarithmic operations for counting and traversing the Trie structure.
What is the space complexity of LeetCode 440. K-th Smallest in Lexicographical Order?: The Python solution on this page uses O(1) since we only use a few variables to track the current prefix and count auxiliary space.
What topics does LeetCode 440. K-th Smallest in Lexicographical Order cover?: LeetCode 440. K-th Smallest in Lexicographical Order is tagged Trie on LeetCode.