Scale Engineer

K-th Smallest in Lexicographical Order

Hard
#0427Time: `O(N * log(N) * D)`, where `N` is `n` and `D` is the maximum number of digits in a number up to `n` (i.e., `D = log10(n)`). Generating the list takes `O(N * D)`. Sorting `N` strings of average length `D` takes `O(N * log(N) * D)`. Given the constraints, this is too slow.Space: `O(N * D)`. We need to store `N` strings, where `N` is `n` and `D` is the maximum number of digits (i.e., `log10(n)`). For `n = 10^9`, this would require an enormous amount of memory, leading to a Memory Limit Exceeded error.3 companies
Data structures
Trie
Companies
SamsungDE ShawHulu

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward approach where we generate all integers from 1 to n, convert them to their string representations, and then sort these strings lexicographically. The k-th smallest number is simply the element at the (k-1)-th index of the sorted list.

Algorithm

  • Create a list of strings.
  • Iterate from i = 1 to n. In each iteration, convert i to a string and add it to the list.
  • Sort the list of strings. Standard library sort for strings is lexicographical.
  • Retrieve the string at index k-1.
  • Convert this string back to an integer and return it.

Walkthrough

This approach, while simple, is not practical for the given constraints. The main bottleneck is the creation and sorting of a list containing up to 10^9 elements. Generating these numbers and storing them as strings would consume gigabytes of memory. Subsequently, sorting this massive list would be computationally prohibitive.

Here is a Java implementation of this approach:

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public int findKthNumber(int n, int k) {        List<String> list = new ArrayList<>();        for (int i = 1; i <= n; i++) {            list.add(String.valueOf(i));        }        Collections.sort(list);        return Integer.parseInt(list.get(k - 1));    }}

Complexity

Time

`O(N * log(N) * D)`, where `N` is `n` and `D` is the maximum number of digits in a number up to `n` (i.e., `D = log10(n)`). Generating the list takes `O(N * D)`. Sorting `N` strings of average length `D` takes `O(N * log(N) * D)`. Given the constraints, this is too slow.

Space

`O(N * D)`. We need to store `N` strings, where `N` is `n` and `D` is the maximum number of digits (i.e., `log10(n)`). For `n = 10^9`, this would require an enormous amount of memory, leading to a Memory Limit Exceeded error.

Trade-offs

Pros

  • Very simple to understand and implement.

  • Correct for small values of n.

Cons

  • Extremely inefficient for large n.

  • Will result in Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE) for the given constraints.

Solutions

class Solution {private  int n;public  int findKthNumber(int n, int k) {    this.n = n;    long curr = 1;    --k;    while (k > 0) {      int cnt = count(curr);      if (k >= cnt) {        k -= cnt;        ++curr;      } else {        --k;        curr *= 10;      }    }    return (int)curr;  }public  int count(long curr) {    long next = curr + 1;    long cnt = 0;    while (curr <= n) {      cnt += Math.min(n - curr + 1, next - curr);      next *= 10;      curr *= 10;    }    return (int)cnt;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem