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
Related Courses
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.
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
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.
;