440. K-th Smallest in Lexicographical Order

Description

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

 

Example 1:

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.

Example 2:

Input: n = 1, k = 1
Output: 1

 

Constraints:

• 1 <= k <= n <= 109

 

Solutions

Solution: Trie

• Time complexity: O((logn)²)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
const findKthNumber = function (n, k) {
  let current = 1;

  const getGap = (left, right) => {
    let gap = 0;

    while (left <= n) {
      gap += Math.min(n + 1, right) - left;
      left *= 10;
      right *= 10;
    }
    return gap;
  };

  k -= 1;

  while (k) {
    const gap = getGap(current, current + 1);

    if (gap <= k) {
      k -= gap;
      current += 1;
      continue;
    }
    current *= 10;
    k -= 1;
  }
  return current;
};