K-th Smallest in Lexicographical Order - Solution & Explanation

Q: Is K-th Smallest in Lexicographical Order easy or hard?

LeetCode classifies this problem as Hard because the optimal solution requires recognizing the implicit lexicographical tree and implementing prefix counting correctly. The algorithm itself is short but the insight behind skipping entire numeric ranges makes it challenging.

Q: K-th Smallest in Lexicographical Order Python/Java solution

Implementations in Python or Java typically use a helper function that counts how many numbers exist between two prefixes (for example between 1 and 2, then 10 and 20, etc.). The algorithm repeatedly moves to the next prefix or deeper into the tree until the k-th number is reached.

Q: How to solve K-th Smallest in Lexicographical Order in O(n)?

A naive solution could generate all numbers from 1 to n, convert them to strings, sort them lexicographically, and pick the k-th element. That approach costs O(n log n) time and O(n) space. Efficient solutions avoid full generation and instead traverse the implicit prefix tree in about O((log n)^2) time.

Q: What is the best approach for K-th Smallest in Lexicographical Order?

The most efficient approach treats numbers from 1 to n as a lexicographical prefix tree and performs a controlled traversal. At each prefix, a counting function determines how many numbers exist under that prefix so entire subtrees can be skipped. This avoids generating all numbers and runs in about O((log n)^2) time with constant space.

Q: Is K-th Smallest in Lexicographical Order asked at Google/Amazon/Meta?

This problem style appears in interviews at large tech companies because it tests prefix reasoning, number ranges, and tree-like traversal without building a full data structure. Variants involving lexicographical ranking or prefix counting have appeared in interviews at Google and Amazon.

Q: What data structure is used in K-th Smallest in Lexicographical Order?

The solution conceptually uses a trie-like prefix tree where each node represents a numeric prefix. The tree is not built explicitly; instead, prefix ranges are counted mathematically to simulate traversal of this structure.

Q: What is the time complexity of K-th Smallest in Lexicographical Order?

The optimal solution runs in O((log n)^2) time and O(1) space. Each step computes how many numbers lie between two lexicographical prefixes, which costs O(log n), and this counting is performed across roughly log n traversal steps.

HardTrie25 min readAsked at: Amazon, Microsoft, Meta +4

Practice this problem

Problem Statement

Given two integers n and k, return the k^th 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 <= 10⁹

Approach Overview

Problem Overview: Given integers n and k, return the k-th smallest number in lexicographical order within the range [1, n]. Instead of sorting numbers as strings (which would be expensive), you navigate the implicit dictionary order of numbers like a prefix tree.

Approach 1: Lexicographical Order Tree Traversal (O((log n)^2) time, O(1) space)

Numbers from 1 to n can be visualized as a prefix tree (similar to a trie) where each node represents a numeric prefix. For example, prefix 1 expands to 10, 11, 12.... Instead of generating all numbers, count how many values exist under a prefix using a helper function that measures the gap between two lexicographical prefixes.

Start at prefix 1. At each step, compute how many numbers lie under the current prefix. If the count is less than or equal to k, skip the entire subtree and move to the next prefix (like 1 → 2). Otherwise, go deeper into the tree (1 → 10). This approach simulates a preorder traversal of the lexicographical tree without building it explicitly. Because each prefix expansion and counting step takes about O(log n) time and you move through roughly log n levels, the overall complexity becomes O((log n)^2).

This technique is efficient even for very large n (up to 10^9) because it skips entire subtrees rather than enumerating numbers. Conceptually it combines ideas from trie traversal and prefix counting.

Approach 2: Binary Search with Counting Function (O((log n)^2) time, O(1) space)

Another strategy treats the lexicographical order as a searchable space and applies binary search. For a candidate number, compute how many numbers from 1..n appear before it in lexicographical order. This counting relies on the same prefix-range calculation used in the tree traversal approach.

Binary search repeatedly narrows the range until the number whose lexicographical rank equals k is found. Each rank computation walks through digit levels and counts valid prefixes, which costs O(log n). With O(log n) binary search iterations, the final complexity remains O((log n)^2).

The method is conceptually clean if you're comfortable with ranking functions, though the traversal approach usually results in simpler code.

Recommended for interviews: The lexicographical prefix traversal is the solution most interviewers expect. It demonstrates that you recognize the implicit 1..n lexicographical structure and can efficiently skip entire branches using prefix counts. A brute-force string sort would be O(n log n) and impractical for large inputs, while the prefix traversal shows strong algorithmic insight.

Approach 1: Approach 1: Lexicographical Order Tree Traversal

This approach involves systematically traversing a conceptual lexicographical tree. Each integer can be considered a node, with its child nodes being its successors in a lexicographical sense. By counting numbers in subtrees, we can determine where the k-th smallest number lies without generating the entire lexicographical list.

The given C implementation finds the k-th smallest number in a lexicographical manner using a tree traversal strategy. The helper function count_steps calculates how many numbers lie between the current root and its next sibling. This counting allows us to decide if we should move down to the next level (using the current root as a prefix) or move to the next sibling node.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(log(n)^2), as we are traversing a tree where we potentially explore and count nodes at each level.
Space Complexity: O(1), since we are not using any additional data structures.

Try this approach in the editor →

Approach 2: Approach 2: Binary Search with Counting Function

This approach leverages binary search combined with a counting function to directly determine the k-th lexicographical number. Instead of constructing the list, we estimate the position of the k-th number by adjusting potential candidates using the count of valid numbers below a mid-point candidate.

This C approach implements a binary search to find the k-th smallest lexicographical number. The count_below function determines how many numbers less than a given prefix exist. Depending on this count, we adjust our binary search to quickly converge on the result.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(log(n)^2), where binary search narrows down potential candidates.
Space Complexity: O(1), minimal variable storage is employed.

Try this approach in the editor →

Approach 3: Trie-Based Counting + Greedy Construction

The problem asks for the \k\-th smallest number in the range [1, n] when all numbers are sorted in lexicographical order. Since n can be as large as 10^9, we cannot afford to generate and sort all the numbers explicitly. Instead, we adopt a strategy based on greedy traversal over a conceptual Trie.

We treat the range [1, n] as a 10-ary prefix tree (Trie):

Each node represents a numeric prefix, starting from an empty root;
Each node has 10 children, corresponding to appending digits 0 \sim 9;
For example, prefix 1 has children 10, 11, ldots, 19, and node 10 has children 100, 101, ldots, 109;
This tree naturally reflects lexicographical order traversal.

root
├── 1
│   ├── 10
│   ├── 11
│   ├── ...
├── 2
├── ...

We use a variable curr to denote the current prefix, initialized as 1. At each step, we try to expand or skip prefixes until we find the \k\-th smallest number.

At each step, we calculate how many valid numbers (i.e., numbers \le n with prefix curr) exist under this prefix subtree. Let this count be count(curr):

If k \ge count(curr): the target number is not in this subtree. We skip the entire subtree by moving to the next sibling:

$curr \leftarrow curr + 1,\quad k \leftarrow k - count(curr)

Otherwise: the target is within this subtree. We go one level deeper:
curr \leftarrow curr times 10,\quad k \leftarrow k - 1

At each level, we enlarge the current range by multiplying by 10 and continue descending until we exceed n.

The time complexity is O(log^2 n), as we perform logarithmic operations for counting and traversing the Trie structure. The space complexity is O(1)$ since we only use a few variables to track the current prefix and count.

Code

Python Java C++Go TypeScript Rust

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Approach 1: Lexicographical Order Tree Traversal	Time Complexity: O(log(n)^2), as we are traversing a tree where we potentially explore and count nodes at each level. Space Complexity: O(1), since we are not using any additional data structures.
Approach 2: Binary Search with Counting Function	Time Complexity: O(log(n)^2), where binary search narrows down potential candidates. Space Complexity: O(1), minimal variable storage is employed.
Trie-Based Counting + Greedy Construction	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Lexicographical Order Tree Traversal	O((log n)^2)	O(1)	Best general solution for large n. Efficiently skips entire prefix ranges.
Binary Search with Counting Function	O((log n)^2)	O(1)	Useful when reasoning about lexicographical rank or implementing rank-based search.

Video Solution

K-th Smallest in Lexicographical Order - Leetcode 440 - Python • NeetCodeIO • 22,452 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is K-th Smallest in Lexicographical Order easy or hard?

LeetCode classifies this problem as Hard because the optimal solution requires recognizing the implicit lexicographical tree and implementing prefix counting correctly. The algorithm itself is short but the insight behind skipping entire numeric ranges makes it challenging.

K-th Smallest in Lexicographical Order Python/Java solution

Implementations in Python or Java typically use a helper function that counts how many numbers exist between two prefixes (for example between 1 and 2, then 10 and 20, etc.). The algorithm repeatedly moves to the next prefix or deeper into the tree until the k-th number is reached.

How to solve K-th Smallest in Lexicographical Order in O(n)?

A naive solution could generate all numbers from 1 to n, convert them to strings, sort them lexicographically, and pick the k-th element. That approach costs O(n log n) time and O(n) space. Efficient solutions avoid full generation and instead traverse the implicit prefix tree in about O((log n)^2) time.

What is the best approach for K-th Smallest in Lexicographical Order?

The most efficient approach treats numbers from 1 to n as a lexicographical prefix tree and performs a controlled traversal. At each prefix, a counting function determines how many numbers exist under that prefix so entire subtrees can be skipped. This avoids generating all numbers and runs in about O((log n)^2) time with constant space.

Is K-th Smallest in Lexicographical Order asked at Google/Amazon/Meta?

This problem style appears in interviews at large tech companies because it tests prefix reasoning, number ranges, and tree-like traversal without building a full data structure. Variants involving lexicographical ranking or prefix counting have appeared in interviews at Google and Amazon.

What data structure is used in K-th Smallest in Lexicographical Order?

The solution conceptually uses a trie-like prefix tree where each node represents a numeric prefix. The tree is not built explicitly; instead, prefix ranges are counted mathematically to simulate traversal of this structure.

What is the time complexity of K-th Smallest in Lexicographical Order?

The optimal solution runs in O((log n)^2) time and O(1) space. Each step computes how many numbers lie between two lexicographical prefixes, which costs O(log n), and this counting is performed across roughly log n traversal steps.

Ready to solve this problem?

Practice K-th Smallest in Lexicographical Order with our built-in code editor and test cases.

Practice on FleetCode

Count Special Integers

Problem Info

DifficultyHard

Acceptance46.2%

Approaches3

Reading time25 min

Asked at

Amazon Microsoft Meta Google De Shaw

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Approach 1: Lexicographical Order Tree Traversal

Code

Complexity

Approach 2: Approach 2: Binary Search with Counting Function

Code

Complexity

Approach 3: Trie-Based Counting + Greedy Construction

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents