440. K-th Smallest in Lexicographical Order - Explanation

Description

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

Example 1:

Input: n = 10, k = 3

Output: 2

Explanation: The lexicographical order is [1,10,2,3,4,5,6,7,8,9]. The third smallest number is 2.

Example 2:

Input: n = 11, k = 3

Output: 2

Explanation: The lexicographical order is [1,10,11,2,3,4,5,6,7,8,9]. The third smallest number is 11.

Constraints:

1 <= k <= n <= 1,000,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        nums = []
        for num in range(1, n + 1):
            nums.append(str(num))

        nums.sort()
        return int(nums[k - 1])

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

2. Prefix Count

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        cur = 1
        i = 1

        def count(cur):
            res = 0
            nei = cur + 1
            while cur <= n:
                res += min(nei, n + 1) - cur
                cur *= 10
                nei *= 10
            return res

        while i < k:
            steps = count(cur)
            if i + steps <= k:
                cur = cur + 1
                i += steps
            else:
                cur *= 10
                i += 1

        return cur

Time & Space Complexity

Time complexity: $O((\log n) ^ 2)$
Space complexity: $O(1)$