Leetcode Daily Question 22/09/2024 - 440. K-th Smallest in Lexicographical Order

Problem Description:

Given integers n, k. Find the kth smallest lexicographic number between [1,n]

class Solution:
  def countNums(self, current, n):
    count = 0
    first = current
    last = current + 1
    while first <= n:
      count += min(n+1, last) - first
      first *= 10
      last *= 10
      
  	return count

  def findKthNumber(self, n: int, k: int) -> int:
    current = 1
    k -= 1
    
    while k > 0:
      count = self.countNums(current, n)
      if count <= k:
        k -= count
        current += 1
      else:
        k -= 1
        current *= 10
    return current

Explanation:

We solve this by counting how many lexicographic numbers (l-nums) are between two consecutive numbers between 1 and possibly 9. This is because l-nums only concern the least significant digit in the number.

For example if we have n = 13. Then the lexico order would be [1,10,11,12,13,2,3,4,5,6,7,8,9].

Here is how the counting works. We start with 1. Between 1 and 2, we need to consider all possible l-nums.

We start with a trivial count at 1. Then we append a digit by multiplying 10 to 1 and 2. So now between 10 and 20, we see that 20 is larger than n, so truncate our count to end at n. This means we need to add n - lower + 1 to our count = 13 + 1 - 10 + (1 from before) = 5.

def countNums(current, n):
  count = 0
  first = current
  lsat = current + 1
  while first <= n:
    count += min(n + 1, last) - first
    first *= 10
    last *= 10
  return count

Now, suppose k = 2, n = 13 as before. Since our counting in 0-indexed, we need to start with k - 1 = 1. We also initiate current = 1

Then while k is not 0, we count how many l-nums are between current and current + 1.

We have 5 l-nums between [1,2), this is larger than k = 1, so we move on to start from 10 and decrement k. However k is now 0, so loop breaks and our final answer is obtained.

Consider if k = 3 instead. Then we would have k = 1 current = 10 at the end of step 1 as before. Step 2, we see that there are 1 l-nums between [10,11) this is equal to k so current = 11 and we subtract count from k to break the loop.

def findKthNumber(n, k):
  current = 1
  k -= 1
  while k > 0:
    count = countNums(current, n)
    if count <= k:
      current += 1
      k -= count
    else:
      current *= 10
      k -= 1
      
  return current

This has time complexity O(log n). This is because we are halving the number of operations each time we count a prefix.

This has space complexity O(1) as we do not store extra data structures in memory.

The full solution can be found near the top of the page.