440. K-th Smallest in Lexicographical Order - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given two integers, n and k, your task is to find the k-th smallest number in the lexicographical order of all integers in the range [1, n].

Lexicographical order means that the numbers are sorted as if they were strings. For example, "10" comes before "2" when compared lexicographically.

Example 1

  • Input: n = 13, k = 2
  • Lexicographical Order: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
  • Output: 10
  • Explanation: The 2nd number in the sorted order is 10.

Example 2

  • Input: n = 1, k = 1
  • Lexicographical Order: [1]
  • Output: 1
  • Explanation: With only one number available, the first (and only) number is 1.

Example 3

  • Input: n = 100, k = 10
  • Lexicographical Order (first few numbers): [1, 10, 100, 11, 12, 13, 14, 15, 16, 17, ...]
  • Output: 17
  • Explanation: Counting through the lexicographical order, the 10th number is 17.

Constraints:

  • 1 ≤ k ≤ n ≤ 10^9
  • The solution must work efficiently given the large possible value of n.

Hints to Guide Your Approach

  1. Think Tree Structure:
    Imagine all numbers from 1 to n arranged in a prefix tree (trie) where each node represents a prefix. Traversing this tree in pre-order gives the lexicographical order.

  2. Count the Nodes:
    Instead of generating every number, you can count the numbers under each prefix. This allows you to skip whole subtrees if the k-th element isn’t within them.

  3. Skip Subtrees:
    If you know that the count of numbers starting with a given prefix is less than k, you can subtract that count from k and move to the next prefix.

Approaches

Approach 1: Brute Force (Generate and Sort)

  • Idea:
    Generate all numbers from 1 to n, convert them to strings, sort them lexicographically, and then pick the k-th element.
  • Steps:
    1. Generate a list of numbers from 1 to n.

    2. Convert each number to a string.

    3. Sort the list based on string order.

    4. Convert the k-th string back to an integer.

  • Why It Falls Short:
    While this approach is easy to implement, it has a time complexity of O(n log n) due to sorting and can use too much memory when n is very large (up to 10^9). This makes it impractical for large inputs.

Approach 2: Optimal Prefix Counting Method

  • Idea:
    Use a counting method that leverages the structure of lexicographical order. Think of the numbers as nodes in a tree where each node (prefix) has children (extended numbers). By counting how many numbers fall under each prefix, you can decide to “skip” entire sections.

  • Steps:

    1. Start with prefix = 1.
      This represents the first number in lexicographical order.

    2. Count the nodes (numbers) under the current prefix:
      Define a helper function count(prefix, n) that counts how many numbers starting with the given prefix are within the range [1, n].

    3. Decide whether to go deeper or move to the next prefix:

      • If the count is less than k, then the k-th number is not in this subtree. Subtract the count from k and move to the next sibling (i.e., prefix + 1).
      • If the count is greater than or equal to k, then the k-th number lies in this subtree. Append a digit (i.e., multiply the prefix by 10) to dive into the next level.
    4. Repeat until k becomes 0.
      The current prefix is your answer.

  • Benefits:
    This method only requires traversing through the tree structure based on digit counts and skips large parts of the search space, leading to an efficient solution with a complexity roughly proportional to O(log n).

Detailed Explanation and Pseudocode

Prefix Counting Helper Function

The helper function calculates how many numbers under a given prefix are ≤ n. Here’s the idea:

  • Initialize curr with the prefix and next with prefix + 1.
  • While curr ≤ n:
    • Add min(n + 1, next) - curr to the count. This gives the count of numbers between curr and next - 1.
    • Multiply curr and next by 10 to move to the next level.

Pseudocode:

function count(prefix, n):
    count = 0
    curr = prefix
    next = prefix + 1
    while curr <= n:
        count += min(n + 1, next) - curr
        curr *= 10
        next *= 10
    return count

Main Logic

set current = 1
decrement k by 1 (since we start from prefix 1)
while k > 0:
    count = count(current, n)
    if count <= k:
        k -= count
        current += 1      // move to next sibling prefix
    else:
        k -= 1
        current *= 10     // move down to the first child in the prefix tree
return current

This loop gradually refines the prefix until k becomes 0, meaning the current prefix is the k-th smallest number.

Python Implementation

Python3
Python3

. . . .

Java Implementation

Java
Java

. . . .

Explanation:

  • The count function calculates how many numbers with the given prefix exist in the range [1, n].
  • In findKthNumber, we adjust k (subtracting 1 initially) and then either skip a whole prefix subtree or move deeper into the tree until we find the k-th number.

Complexity Analysis

  • Time Complexity:
    The while loop in the optimal approach runs roughly proportional to the number of digits in n (i.e., O(log n)). In each iteration, the helper function may traverse a few levels, but overall the time complexity is efficient.

  • Space Complexity:
    O(1) – Only a constant amount of extra space is used regardless of the size of n.

Common Mistakes

  • Off-by-One Errors:
    Not adjusting k properly (remember to decrement k by 1 at the start because the counting includes the current prefix).

  • Incorrect Count Calculation:
    Failing to correctly calculate the number of numbers under a given prefix can lead to skipping too many or too few nodes.

  • Integer Overflow:
    In Java, using int for calculations in the counting function can overflow; hence, use long for intermediate counts.

Edge Cases

  • n = 1:
    The only number is 1, so the answer should be 1 regardless of k.
  • k = 1:
    The first number in lexicographical order is always 1.
  • Large n:
    The algorithm is designed to handle large values of n efficiently by skipping entire subtrees.
  • Variations:
    • Find the k-th largest in lexicographical order.

    • Return the entire lexicographical order for a given n.

  • Related Problems for Further Practice:
    • Lexicographical Numbers: Explore problems that involve lexicographical ordering.
    • Trie-Based Problems: Practice problems that require working with prefix trees.
    • Binary Search Problems: Problems that require skipping or counting ranges (e.g., finding the k-th missing number).
TAGS
LeetCode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
How to succeed at coding interviews?
4. Median of Two Sorted Arrays - Detailed Explanation
Learn to solve Leetcode 4. Median of Two Sorted Arrays with multiple approaches.
How to explain code in interview?
Related Courses
Image
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Image
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Image
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;